[백준 2352] 반도체 설계 [C]

백준 - 2352

---

풀이

"백준 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);
}

---

출처 및 참고자료

2352번: 반도체 설계

 

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