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

algorithm : DP , lower_bound

 

해설

O(N * N) LIS로 풀면 시간 초과가 나오는 문제이다 그렇기 때문에 다른 방법을 생각해보아야 한다

O(N log N) 시간을 줄여야 한다. lower_bound = O(log N)

 

초기값

10

50

45

60

35

100

 

LIS

10

10이 LIS 중 가장 큰 값이기 때문에 10을 push_back 합니다

 

                                                        ↓

 

10

50

50이 LIS중 가장 큰 값이기 때문에 50을 push_back 합니다

 

                                                        ↓

10

45

45는 LIS 중 가장 큰 값이 아닙니다 10 보다는 크고 50보다는 작은 수입니다 그렇기 때문에 45보다 작은

수중 가장 가까운 수인 10 뒤 2번째 배열에 50을 빼고 45를 추가한다

 

                                                        ↓

10

45

60

60이 LIS 중 가장 큰 값이기 때문에 60을 push_back 합니다

 

                                                        ↓

 

10

35

60

30은 배열중 자기보다 작고 30이랑 가까운 10 뒤에 45를 지우고 35를 넣는다

 

                                                        ↓

10

35

60

100

100이 LIS 중 가장 큰 값이기 때문에 100을 push_back 합니다

 

이제 여기서 얻은 LIS를 그냥 출력하면 오답이 나온다 자기가 어디서 왔는지 path가 중요하다

 

path를 채우는 방법은 밑에 그림과 같다

35가 들어올 때 경우이다. 자기 배열 처음부터 자기 it까지 거리를 구하면 된다

이런 식으로 구했을 때 밑에 그림처럼 path가 구해진다

path 배열 뒤에서부터 가장 큰 값이 4를 출력한다음 4,3,2,1 순서대로 가면서 그 위치에 있는 arr를 ans 배열에 넣는다

ans는 뒤에서 부터 넣었기 때문에 출력할 때는 reverse 해서 출력했다

#include<bits/stdc++.h>
#define LM 1000000+10
#define INF 199999999
using LL = long long;
using namespace std;

int N;
int arr[LM];
int path[LM];
int chk[LM];
int len;
vector<int> v,ans;

void input(){
    scanf("%d",&N);
    for(int i = 1 ; i <= N ; i++)
        scanf("%d",&arr[i]);
}

void DP(){
    v.push_back(-2000000000);
    for(int i = 1 ; i <= N; i++){
        auto it = lower_bound(v.begin(),v.end(),arr[i]);
        path[i] = it - v.begin();
        if(it == v.end()) v.push_back(arr[i]);
        else *it = arr[i];
    }
}

void trace(){
    int len = v.size() - 1;
    printf("%d\n",len);
    for(int i = N ; i >= 1 ; i--){
        if(len == path[i]){
            ans.push_back(arr[i]);
            len--;
        }
    }
    reverse(ans.begin(),ans.end());
    for(auto a : ans)
        printf("%d ",a);
}
int main(){
    //freopen("input.txt","r",stdin);
    input();
    DP();
    trace();
    return 0;
}