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

백준 - 12738

---

풀이

"백준 12015, 가장 긴 증가하는 부분 수열 2"와 동일하지만, 입력받는 숫자들의 범위가 더 크다.

기존 코드로 풀린다.

---

소스코드

#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);
}

---

출처 및 참고자료

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

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