[2023-06-03] 백준 11053 가장 긴 증가하는 부분 수열

[Silver II] 가장 긴 증가하는 부분 수열 - 11053

문제 링크

성능 요약

메모리: 14472 KB, 시간: 144 ms

분류

다이나믹 프로그래밍

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

1) 내가 시도한 코드

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        ArrayList<Node>[] arr = new ArrayList[N+1];

        for(int i = 0; i < N+1; i++)
            arr[i] = new ArrayList();

        for(int i = 0; i < N; i++)
            arr[1].add(new Node(Integer.parseInt(st.nextToken()), i));

        /*
    10 20 10 30 20 50
    1 -> 10 20 30 50
    -> 20 30 50
    -> 30 50
    -> 50
    -> x

    1 -> 10 20 10 30 20 50
    -> 10 60 50 30 70 100 20
    -> 60 50 30 70 100 20
    -> 70 70 70 100 100
    -> 100
    -> x
    */
        for(int i = 2; i < N+1; i++) {
            for(Node n : arr[i-1]) {
                for(int j = n.index; j < arr[1].size(); j++) {
                    boolean b = true;
                    Node tmp = arr[1].get(j);
                    //이미 있는 녀석이면 제외
                    for (Node k : arr[i]) {
                        if (k.index == tmp.index) {
                            b = false;
                            break;
                        }
                    }
                    if(b && (n.val < tmp.val)) arr[i].add(new Node(tmp.val, tmp.index));
                }
            }
            if(arr[i].isEmpty()) {
                System.out.println(i-1);
                return;
            }
         }

        System.out.println(N);


    }

    public static class Node {
        int val;
        int index;

        public Node(int val, int index) {
            this.val = val;
            this.index = index;
        }
    }
}

처음 접근했던 방법은 단순 무식했던 것 같다. DP로 짜려고 시도했지만 DP가 되지 않고, DFS가 되버린 느낌.. 일단 처음에 모든 값들을 넣어 준 다음, 그 값을 기준으로 그 값보다 index가 크며, 그 값보다 큰 값들을 ArrayList[i]에 추가해주었다. 만약 추가가 되지 않아 빈 ArrayList[i]라면 그 전 값이 최대 길이이라는 것이기 때문에 i-1을 출력해주는 방식으로 구현하였다. 그러니, 시간 초과가 났다. 시간 복잡도를 계산해보니 1000 * 2 + 1000 * 1000 * 3 * 1000.. 대략 30억 정도의 연산을 도는 것이었다. 짜고나니 DFS.. 느낌이었다. 결국 친구의 도움을 받아 해결하였다.

2) 정답 코드

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;

        // arr 맨 처음 값이 담길 array
        int[] arr = new int[N];
        // dp 횟수 값이 담길 array
        int[] dp = new int[N];
        st = new StringTokenizer(br.readLine());
        // 모든 dp 값을 1로 초기화
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        // i는 현재 index, j는 i전까지의 index
        // 만약 arr[i]보다 arr[j]가 작다면(arr[j] 다음 부분 원소가 arr[i]가 될 수 있음)
        // dp[j] + 1과 dp[i] 중 큰 값으로 dp[i] 초기화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if(arr[i] > arr[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int ans = -1;
        for(int i = 0 ; i < N; i++)
            ans = Math.max(ans, dp[i]);

        System.out.println(ans);
    }

}

---

 느낀점

DP라 함은 DP 테이블을 꼭 두고 생각을 해보자고 다짐하게 되었다. 점화식과 DP 테이블이 가장 중요한 것 같다. 더 많은 DP 문제를 풀어보며 형태를 익혀봐야겠다