[BOJ] 12015. 가장 긴 증가하는 부분 수열2

LIS의 대표적인 예제이다.

이 문제같은 경우 11053번(링크)와 다르게 n의 범위가 1000000까지라 lower_bound를 사용하는 LIS문제 유형이다. Java의 경우 lower_bound를 따로 제공해주지 않기에 직접 구현하여 사용하였다.

lower_bound를 사용하는 LIS경우 LIS배열을 생성하는데 이때 LIS[i]의 값은 i만큼의 길이의 최장 증가 수열에서 가지게 되는 가장 작은 마지막 원소값을 의미하게 된다. 즉 위의 예제 입력을 예로 들면 LIS[2]는 최장 증가 수열 길이가 2일때 가지는 경우의 수 가 10 20, 10 30, 10 50, 20 30, 20 50 등이 있는데 이때 가장 작은 마지막 원소값은 10 20에서의 20이 되게 된다. 따라서 LIS[2] = 20을 가지게 된다. 이원리는 일단 LIS[cur]와 arr[i]를 비교하여 만일 1. LIS[cur] < arr[i]인 경우 arr[i]값을 LIS[++cur]에 넣어주게 되는 것이고, 2. LIS[cur] >= arr[i] 인경우 lower_bound의 값을 찾아서 LIS[lower_bound]를 갱신해주는 것이다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
//https://wordbe.tistory.com/entry/DP-LIS-%EC%B5%9C%EC%9E%A5-%EA%B3%B5%ED%86%B5-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4
public class Main_bj_12015_가장긴증가하는부분수열2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        int N = Integer.parseInt(br.readLine());
 
        int[] LIS = new int[N + 1];        //LIS[i]는 i만큼 길의의 최장 수열에서 가질 수 있는 가장 작은 arr의 원소값
        int[] arr = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int cur = 0;
 
        for (int i = 0; i < N; i++) {
            if (LIS[cur] < arr[i]) {
                cur += 1;
                LIS[cur] = arr[i];
            } else {
                int lowerBound = lowerBound(LIS, cur, arr[i]);
                LIS[lowerBound] = arr[i];
            }
        }
 
        for (int li : LIS) {
            System.out.println("li = " + li);
        }
 
        System.out.println(cur);
    }
 
    static int lowerBound(int[] LIS, int curIndex, int value) {
        int startIndex = 0;
        int endIndex = curIndex;
 
        while (startIndex < endIndex) {
            int midIndex = (startIndex + endIndex) / 2;
 
            if (LIS[midIndex] < value) {        //현재값이 찾는값보다 작을때
                startIndex = midIndex + 1;
            } else {
                endIndex = midIndex;
            }
        }
 
        return endIndex;
    }
}