[PS] BOJ12015 가장 긴 증가하는 부분수열2 ( LIS ) with JAVA

12015번: 가장 긴 증가하는 부분 수열 2

 

 

◎ 문제풀이 

 

DP는 수열에서 나올 수 있는 부분수열의 모든 경우에서 조건에 맞는 경우를 구하는 문제이다. 이때, 부분수열의 조건이 '가장 길고'(Longest) '증가하는'(Incresing) 부분수열(Subsequence)를 구하는 문제라면,  LIS( Longest Increasing Subsequence) 알고리즘 풀이라 생각하면 된다.

 

처음에 이중for문을 만들어서 접근하였는데, 시간초과가 발생했다. 수열의 크기가 최대 1,000,000이므로 이중for으로 접근해서는 안된다. 한번의 반복으로 최장부분수열을 만들어야 한다. 한 번의 방법으로 최장부분수열을 만들며 최적의 답을 찾아가는 Greedy 접근을 해야 한다.

 

 

 

 

처음 10은 최장부분수열에 바로 추가한다.

 

 

 

 

20은 최장부분수열의 끝값(10)보다 크니 최장부분수열에 추가한다.

 

 

 

10은 최장부분수열의 끝값(20)보다 작다.

여기서 최장부분수열 형성의 가장 중요한 원리가 등장한다. 

 

부분수열의 길이가 최장이 되려면 수와수 사이가 촘촘해야 한다. 10 50 보다 10 20이 더 촘촘하다. 즉, 최장부분수열은 가장 촘촘히 구성된 수열을 의미한다. 촘촘하면 촘촘할수록 더 많은 수가 들어올 수 있는 최적의 최장부분수열이 된다.(Greedy)  고로, 최장부분수열의 끝값보다 작다는 의미는 최장부분수열을 더 촘촘하게 만들 수 있다는 의미이다.  최장부분수열을 탐색하여 같거나 가장 가까운 큰수를 탐색하고 수를 바꾸어 최장부분수열을 촘촘하게 만든다.( 이분탐색 ) 

 

위 경우는 10이니 10을 10으로 바꾼다. 

 

 

 

 

30과 50은 끝값보다 크니 바로 추가한다. 그리고 37이 나왔다. 37은 끝값인 50보다 작다. 그러므로 37은 최장부분수열은 더 촘촘하게 만들수 있다. 최장부분수열에서 37과 같거나 가장 가까운 큰수를 탐색한다.(이분탐색) 50이므로 50을 37로 바꾸어 촘촘하게 만든다.

 

 

 

 

이렇게 최적의 최장부분수열이 완성되었다.

 

부분수열의 최장 길이를 구하는 문제로 촘촘할수록 최장부분수열이 된다는 원리를 발견하고 이를 Greedy로 접근한 뒤 이분탐색으로 탐색해야 하는 난이도 있는 문제였다.

 

 

◎코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

//BOJ12015 가장 긴 증가하는 부분 수열 2
public class Main {

    static List<Integer> lis = new ArrayList<>();
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        arr = new int[n];

        for (int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        lis.add(0); 
        for (int i=0; i < n; i++) {
            if (arr[i] > lis.get(lis.size()-1)) lis.add(arr[i]); // 끝값보다 크면 최장부분수열 끝에 추가하기
            else {
                int index = binarySearch(0,lis.size()-1,arr[i]); //끝값보다 작으면 이분탐색
                lis.set(index,arr[i]); // 촘촘하게 만들기
            }
        }

        System.out.println(lis.size()-1); // 처음에 추가했던 0 빼기 (-1)
    }

    // 이분탐색
    public static int binarySearch(int start, int end, int value){
        if(start == end ) return end; //같거나 가장 가까운 큰수 

        int mid = ( start + end )/2;
        if( lis.get(mid) >= value ) return binarySearch(start, mid, value);
        else return binarySearch(mid+1,end,value);

    }
}