728x90
풀이
부분 수열의 최대 길이를 구한 후 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번: 책정리
동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터
www.acmicpc.net
[백준 12015] 가장 긴 증가하는 부분 수열 2 [C]
풀이 "백준 11053, 가장 긴 증가하는 부분 수열"보다 수열의 크기가 커, 기존의 방법대로 하면 시간초과가 발생한다. 수열 전체에서 binary search로 특정한 조건의 부분 수열을 탐색하는 방법은 아닌
kyr-db.tistory.com
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 1377] 버블 소트 [C] (0) | 2021.09.05 |
|---|---|
| [백준 17404] RGB거리 2 [C] (0) | 2021.09.05 |
| [백준 12738] 가장 긴 증가하는 부분 수열 3 [C] (0) | 2021.09.04 |
| [백준 14003] 가장 긴 증가하는 부분 수열 5 [C] (0) | 2021.09.04 |
| [백준 12015] 가장 긴 증가하는 부분 수열 2 [C] (0) | 2021.09.04 |