백준 12738번: 가장 긴 증가하는 부분수열 3 (JAVA)

https://www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

문제

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

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

입력

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

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

출력

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

 

---

 

풀이

가장 기본적인 LIS 풀이는 O(N^2) 알고리즘이라, 본 문제의 N size - 100만 - 에 대해서는 시간 초과가 뜰 수밖에 없습니다. 따라서 O(NlogN) LIS 풀이를 사용할 필요가 있습니다.

 

res라는 int array를 다음과 같이 정의한다:

 - res[i]: 길이가 i인 LIS 중 가장 작은 마지막 원소의 값

 

0부터 수열의 길이 N-1까지 for문을 돌면서, 각 위치에서의 LIS를 찾는 과정을 합니다.

현 위치를 i라고 가정합니다. 그러면, i 이전의 LIS의 최댓값은 i입니다(코드에서는 'size'라는 변수를 통해 LIS의 길이를 기록하여 살짝 더 최적화를 했습니다.)

 res는 현재 LIS 길이 범위 내에서 monotonically increasing sequence(단조증가수열)이기에(증명: 간단한 관찰), 현재 위치에서의 값보다 작은 값 중 가장 큰 값을 찾는 과정을 이진탐색으로 구현하면 logN번의 연산 안에 찾을 수 있습니다.

 

스스로 정리해본다고 말로 살짝 풀어서 써보았는데, 과정을 이미지/영상을 통해 보는 것이 가장 이해하기 쉬울 듯합니다.

 

 

풀이

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));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N], res = new int[N+2], nums = new int[N];
        Arrays.fill(dp, 1); // 현 위치에서 LIS는 최소 1
        Arrays.fill(res, Integer.MAX_VALUE); // 0번째 index는 신경 안써도 됨
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int ans = 1;
        res[1] = nums[0];
        int size = 1; // 현재 LIS
        for (int i = 1; i < N; i++) {
            int start = 1, end = size;
            while (start <= end) {
                int mid = (start + end) / 2;
                if (res[mid] >= nums[i]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
            int lis = end + 1;

            dp[i] = lis;
            if (lis > size) size++; // 더 큰 IS를 찾으면 size를 늘린다.
             // 같은 길이의 IS면서 가장 작으면 뒤의 for문에서는 해당 값을 기준으로 IS로 만들 수 있음.
            if (nums[i] < res[lis]) res[lis] = nums[i];
            if (ans < lis) ans = lis; // 수열 전체에 대해서 가장 큰 IS를 찾는다.
        }

        System.out.println(ans);
    }

}