[백준 14003] 가장 긴 증가하는 부분 수열 5 [C]

백준 - 14003

---

풀이

"백준 12015, 가장 긴 증가하는 부분 수열 2"에서 부분 수열의 최대 길이를 lower bound방식으로 빠르게 구했지만,

이렇게 만들어진 임의의 수열들의 요소가 최대 길이를 이루는 요소들이 아님을 예시를 통해 알 수 있었다.

 

한마디 더 붙이자면, 임시로 생성하는 수열의 최댓값보다 작은 경우에는 lower bound으로 찾은 index위치에 덮어쓰기 때문에 최대 길이를 이루는 요소가 아님을 알 수 있다.

 

만약 입력받은 요소들이 몇 번째 index에서 덮어쓰기가 되는지 알 수 있다면, 이전의 방법으로 구한 부분 수열의 최대 길이와, 입력받은 요소의 개수 N을 조건에 따라 줄여가면, 요소들을 구할 수 있다.

---

소스코드

#include <stdio.h>
#define MAX 1000001
int arr[MAX], temp[MAX], dp[MAX] = {1000001};

void print(int back, int idx){
    if (idx == -1) return;
    if (temp[idx] == back){
        print(back - 1, idx - 1);
        printf("%d ", arr[idx]);
    }else print(back, idx - 1);
}
int main(){
    int N;
    scanf("%d", &N);
	
    int val, back = 0;
    for(int i = 0; i < N; i++){
        scanf("%d", &val);
        arr[i] = val;
		
        if(val > dp[back]){
            dp[++back] = val;
            temp[i] = back;
        }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;
            temp[i] = idx;
        }
    }
    printf("%d\n", back+1);
    print(back, N-1);
}

---

출처 및 참고자료

14003번: 가장 긴 증가하는 부분 수열 5

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

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)