728x90
풀이
"백준 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
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
www.acmicpc.net
[백준 12015] 가장 긴 증가하는 부분 수열 2 [C]
풀이 "백준 11053, 가장 긴 증가하는 부분 수열"보다 수열의 크기가 커, 기존의 방법대로 하면 시간초과가 발생한다. 수열 전체에서 binary search로 특정한 조건의 부분 수열을 탐색하는 방법은 아닌
kyr-db.tistory.com
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 17404] RGB거리 2 [C] (0) | 2021.09.05 |
---|---|
[백준 1818] 책 정리 [C] (0) | 2021.09.04 |
[백준 14003] 가장 긴 증가하는 부분 수열 5 [C] (0) | 2021.09.04 |
[백준 12015] 가장 긴 증가하는 부분 수열 2 [C] (0) | 2021.09.04 |
[백준 9466] 텀 프로젝트 [C] (0) | 2021.09.04 |