[백준 1818] 책 정리 [C]

백준 - 1818

---

풀이

부분 수열의 최대 길이를 구한 후 N에서 빼주면 된다.

---

소스코드

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

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", N - (back + 1));
}

---

출처 및 참고자료

1818번: 책정리

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