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

백준 - 12015

---

풀이

"백준 11053, 가장 긴 증가하는 부분 수열"보다 수열의 크기가 커, 기존의 방법대로 하면 시간초과가 발생한다.

수열 전체에서 binary search로 특정한 조건의 부분 수열을 탐색하는 방법은 아닌 것 같아 lower bound만을 이용했다.

 

다음과 같이 수열의 길이만을 계산하기 위해 다음과 같이 수열을 만들었다.

• i = 0이거나, 생성 중인 수열의 가장 뒷 값보다 큰 경우에는 길이를 늘려준다.
• 위의 조건이 아닐 때마다, lower bound로 적절한 위치에 입력받은 값을 삽입한다.

10 20 10 11 20 와 같은 수열을 입력 받았다고 가정하자.

앞에서 순차적으로 값이 커지는 경우만 계산을 한다면 10 20으로 최대 길이가 2다.

때문에, 11처럼 20보다는 작지만, 10보다는 큰 경우 즉, 생성 중인 수열의 가장 뒷 값보다 작은 경우에는 부분 수열의 최대 길이에 관해 갱신해 줄 필요성이 있다.

 

다음과 같이 수열을 생성할 것이다.

10       // 1번 조건에 의해 i = 0 이기 때문에 삽입.
10 20    // 1번 조건에 의해 10보다 크기 때문에 삽입.
10 11    // 2번 조건에 의해 lower bound에 11을 삽입.
10 11 20 // 1번 조건에 의해 11보다 크기 때문에 삽입.

단, 이렇게 생성된 부분 수열의 요소들이 항상 최대 길이를 이루는 수열의 요소는 아니다.

ex) 10 12 20 11 30 일 경우 10 11 20 30인 수열이 만들어진다. (정답 : 10 12 20 30)

---

소스코드

#include <stdio.h>
int dp[1000001] = {1000001};

int main(){
    int N;
    scanf("%d", &N);
	
    int val, back = 0;
    for(int i = 0; i < N; i++){
        scanf("%d", &val);
		
        if(val > dp[back]) dp[++back] = val;
        else{
            int left = 0, right = back, mid, idx;
			
            while(left <= right){
                mid = (left+right) / 2;
                if (dp[mid] >= val) right = (idx = mid) -1;
                else left = mid + 1;	
            }
            dp[idx] = val;
        }
    }
    printf("%d", back + 1);
}

---

출처

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