[DP/자바] 코드트리 IL. 최대 증가 부분 수열

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

ans[i]가 i번째 숫자까지를 기준으로 최대 길이라고 할 때, ans[i-1]에서 ans[i]를 무조건 알 수 있다 할 수 없다고 판단하여 그리디는 아니라고 판단했다. 그러면 완전탐색이냐 할 때에 n이 1,000 이하의 수인데, 총 1000개의 숫자 중 최장 길이의 부분 수열을 구하기 위해서는 길이 1부터 n까지의 루프 속에서 해당 길이의 숫자를 선택하는 모든 경우를 탐색하기 위해 백트래킹을 걸면 2^n정도로 걸리는 게 일반적이라 이번 문제에서는 부적절하다 보았다.

 

동적계획법으로 풀게 되면 ans[i]를 구한다 할 때, 0부터 i까지의 숫자 j를 이용하여 arr[i] > arr[j]일 때 ans[i] = Math.max(ans[i], ans[j]+1) 과 같이 점화식을 구할 수 있고, 이렇게 하면 시간복잡도도 O(n^2)에 불과하므로 1,000ms를 초과하지 않는다. 따라서 동적계획법으로 풀었다.

 

문제 풀이

중요한 것은, 기본적으로 모든 숫자는 최소한 길이 1의 부분 수열 길이를 가질 수 있는 것이므로, dp의 모든 항을 1로 초기화해주었다는 점이다. 그리고 모든 항이 만약 내림차순으로 구성되면 pq에 추가되는 숫자가 없기 때문에 이를 고려하지 않으면 IndexErrorException이 발생하므로 pq에 1을 기본적으로 추가해주는 것이 필요했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int n;
    private static int[] arr;
    private static int[] dp;

    private static Queue<Integer> pq = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        /*
        * 중요한 것은, 숫자가 연속될 필요는 없다는 것
        * */
        init();
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    pq.add(-dp[i]);
                }
            }
        }
        System.out.println(-pq.poll());


    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        dp = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
        }
        pq.add(-1);
    }
}