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

11053, 12015, 12738 모두 같은 입력 같은 출력을 하지만

 

범위만 다르다!

	11053	12015	12738
수열A 크기	1 ~ 1,000	1 ~ 1,000,000	1 ~ 1,000,000
수열 A 요소의 범위	1 ~ 1,000	1 ~ 1,000,000	-1,000,000,000 ~ 1,000,000,000

 

[백준] 11053 가장 긴 증가하는 부분 수열

11053을 공부할때 Dp로 푸는 방법과 이진 탐색을 이용해서 푸는 방법을 공부 했었다.

 

11053에서는 DP를 이용해도 범위가 작기 때문에 통과할 수 있지만

12015, 12738 에서는 범위가 백만이상 넘기때문에 DP를 사용하면 시간초과가 발생한다.

 

따라서 이진탐색을 이용해서 문제를 풀면 쉽게 해결할 수 있다.

C++에서는 이진탐색 라이브러리인 lower_bound를 이용하면 아주아주 쉽게 해결할 수 있다. ㅎ

 

 

□ 이진 탐색 코드

void best12015(){
    int n;
    scanf("%d",&n);
    
    vector<int> array;
    for(int i=0;i<n;i++){
        int num;
        scanf("%d",&num);
        array.push_back(num);
    }   
    
    vector<int> lis;
    lis.push_back(array[0]);
    for(int i=0;i<n;i++){
        if(lis.back() < array[i]){
            lis.push_back(array[i]);
        }
        else{
            long index = distance(lis.begin(), lower_bound(lis.begin(), lis.end(), array[i]));
            lis[index] = array[i];
        }
    }
    printf("%d\n",lis.size());   
}