[백준] 12015번 - 가장 긴 증가하는 부분 수열 2 (Gold 2)

문제 링크

백준 12015번 - 가장 긴 증가하는 부분 수열 (Gold 2)

문제 설명

수열 A가 주어져 있을 때, 가장 긴 증가하는 부분 수열의 길이를 출력한다.

주의점

시간복잡도 $O(N\log N)$으로 해결해야한다.
단순하게 끝 항목이 정해진 증가하는 부분 수열의 길이로 DP를 수행한다면, 시간복잡도는 $O(N^2)$이다.

정답 코드 및 설명

이 문제 역시 구글링을 통해 힌트를 받아서 풀었다.
수열 A[1] ~ A[i]의 길이 x인 증가하는 부분 수열의 마지막 원소로 가능한 최솟값을 $f(i, x)$라 두자.
길이 x인 증가하는 부분 수열을 찾을 수 없다면, $f(i, x)$를 아주 큰 수로 둔다.
이 문제에서는 수열의 원소가 1000000까지이므로, 1000001로 두었다.
그러면 $x < y$ 이면 $f(i, x) < f(i, y)$이므로, 이분탐색을 적용할 수 있다.
DP를 통해 $f(i, x)$를 구하는 과정은 코드에 주석으로 달아두었다.

맨 앞에 인덱스 0을 추가한 것은 $f[x] < a[i-1]$인 최대의 $x$를 찾는 과정때문이다.
이를 추가하지 않는다면 모든 $x$에 대해 $f[x] \geq a[i-1]$인 경우를 해결할 수 없다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        final int DEFAULT = 1000001;
        // f(i, x) : a[1] ~ a[i]의 길이 x인 증가하는 부분 수열의 끝 원소의 최솟값
        // lis(i) : a[1] ~ a[i]의 증가하는 부분 수열의 최대 길이
        int f[] = new int[n + 1], lis = 0;
        f[0] = 0;
        // 아주 큰 수로 초기화(어떤 수열의 원소보다도 크면 충분)
        for (int i = 1; i <= n; i++)
            f[i] = DEFAULT;

        int start, end, mid;
        for (int i = 1; i <= n; i++) {
            start = 0;
            end = lis;
            // f(i, x) <= f(i, y) if x <= y
            // f(i, x) = f(i-1, x) if a[i] <= f(i-1, x-1)
            // f(i, x) = min{a[i], f(i-1, x)} if f(i-1, x-1) < a[i]
            if (a[i - 1] > f[lis]) {
                f[lis + 1] = a[i - 1];
                lis++;
            } else {
                // f[x] < a[i-1]인 최대의 x 찾기
                while (start + 1 < end) {
                    mid = (start + end) / 2;
                    if (f[mid] >= a[i - 1])
                        end = mid;
                    else
                        start = mid;
                }
                if (a[i - 1] < f[end])
                    f[end] = a[i - 1];
            }
        }
        bw.write(lis + "");
        bw.close();
    }

}