[백준] 12738번 가장 긴 증가하는 부분 수열3

문제 설명

• https://www.acmicpc.net/problem/12738
• Gold 2
• 풀이시간 : 20분

문제 풀이

• 전통적인 다이나믹 프로그래밍이다.
• LIS 풀이는 O(N^2), O(NlogN)알고리즘이 존재하지만 이 문제에선 후자를 사용해야한다.
• 각 방법별 풀이는 아래와 같다.

1. O(N^2) 알고리즘

• DP[i] : i번째 원소를 마지막으로하는 LIS 길이
• DP[i] : 0~i-1 인덱스의 원소들을 순회하며, i번째 원소보다 값이 작은 것 중 가장 큰 DP값 + 1

2. O(NLogN) 알고리즘

• 위 알고리즘에서 0~i-1 원소를 순회하는 과정을 이분 탐색으로 대체했다고 보면된다.
• DP[i] : i+1 길이의 LCS를 만들 수 있는 마지막 원소 중 가장 작은 값.
• 수열의 원소들을 순회하며 아래 과정 반복함
  1. DP 배열에서 arr[index]값의 lower bound를 찾아서 그 자리를 arr[index]로 바꾼다. (특정 길이의 LIS의 마지막원소를 더 작은 값으로 대체함)
  2. 해당 lower bound가 현재 len(배열의 크기를 나타냄)과 같다면 len증가시킴.
• 위 과정을 마지막 원소까지 반복한 후 len이 가장 긴 증가하는 부분 수열 길이가 된다.

소스 코드 (JAVA)

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

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static int N;
    static int[] arr, dp;

    // value 이상인 원소가 처음 등장하는 위치
    static int lowerBound(int lo, int hi, int value) {
        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (dp[mid] < value) lo = mid;
            else if (dp[mid] > value) hi = mid;
            else hi = mid;
        }
        return hi;
    }

    // DP[i] : 길이가 i+1인 증가하는 부분 수열을 만들 수 있는 마지막 원소 중 가장 작은 값
    static void solve() throws IOException {
        int len = 0;
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 0; i < N; i++) {
            int cur = arr[i];
            int ind = lowerBound(-1, len + 1, cur);
            dp[ind] = cur;
            if (ind == len) len++;
        }
        bw.write(len + "\n");
        bw.flush();
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}

/**
 * 가장 긴 증가하는 부분 수열3 (16:39)
 *
 * - 수열A가 주어졌을 때, 가장 긴 증가하는 부분 수열 길이 출력
 * - N : 수열 크기 (<=100만)
 * - 10억 <= 각원소 <= 10억
 */