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

https://www.acmicpc.net/problem/14003

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

<문제>

O(NlogN)에 최적해 역추적까지, 가장 긴 증가하는 부분수열 1~5를 모두 포함하는 문제라 할 수 있겠다.

lower_bound를 써서 적절한 위치를 O(logN)만에 찾고, 이를 '오름차순'을 유지하도록 넣어주면 된다.

오름차순을 유지하지 못하면, 당연히 이분탐색 기반의 lower_bound도 사용할 수 없기 때문이다.

 

또한, 우리는 하나의 입력을 받고 그 입력에 대해서 최적해를 갱신한다.

즉, 이후의 수열은 전혀 알지 못하는 상태에서 적절한 위치를 선정해줄 필요가 있다.

예를들어,

6
1 2 3 7 5 6 같은 입력이 들어온다고 보자.

{1,2,3,7}까지 순차적으로 갱신되는것은 분명하다.

이후에 5라는 입력이 들어오면, {1,2,3,7}로 구성된 수열은 {1,2,3,5}로 갱신된다.

어처피 {1,2,3,7}이나 {1,2,3,5}나 길이는 4개로 동일하지만, 이부분은 약간 그리디한 느낌으로 접근한다.

우리는 다음에 100만같이 큰 수가 들어오는지도 모르고, 6같이 아슬아슬한 수가 들어오는지도 모른다.

1)길이가 다르다면, 큰쪽을 우선한다. -> 이부분은 그리디는 아니지만

2)길이가 같다면, 다음에 올 수 있는 수의 범위를 최대화한다. -> 이부분이 그리디적인 접근이다

 

이 그리디한 접근으로, 6이라는 입력이 들어오면 {1,2,3,5,6}으로 최적해가 5, 올바르게 답을 구할 수 있겠다.

<소스코드>

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector <int> v;
vector <int> path; 
int a[1000001],check[1000001];
int main(void) {
    int n,i,j,cnt=0;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        auto idx = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        check[i] = idx;
        if (idx + v.begin() == v.end()) {//최대 갱신
            v.push_back(a[i]);
            cnt++;
        }
        else v[idx] = a[i];
    }
    printf("%d\n", cnt);
    vector <int> ans;
    for (i = n - 1; n >= 0; i--) {
        if (cnt < 1)break;
        if (check[i] == cnt - 1) {
            ans.push_back(a[i]);
            cnt--;
        }
    }
    while (!ans.empty()) {
        printf("%d ", ans.back());
        ans.pop_back();
    }
    return 0;
}