[ 백준 ] 14002번 - 가장 긴 증가하는 부분 수열 4 (C++)

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

14002번: 가장 긴 증가하는 부분 수열 4

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175?category=1064608 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

 

1. order배열에 각 수의 LIS에서의 위치를 저장합니다.

 

2. order배열의 끝에서부터 처음까지 for문을 통해 LIS의 cnt = 길이의 숫자로 갱신해주고, order [ i ] == cnt를 만나면 ans에 저장해주고, cnt--를 해줍니다.

 

3. 마지막에 ans에 저장된 숫자들을 차례대로 출력해줍니다.

 

[ 소스코드 ]

 

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N;
int arr[1000];
int order[1000];    //헤당 idx의 숫자의 LIS에서의 순서
vector<int> ans;    //최장 부분 증가 수열
vector<int> LIS;    //lower_bound
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    LIS.push_back(arr[0]);
    order[0] = 1;
 
    for (int i = 1; i < N; i++) {
        if (LIS[LIS.size() - 1] < arr[i]) {
            LIS.push_back(arr[i]);
            order[i] = LIS.size();
        }
        else {
            auto it = lower_bound(LIS.begin(), LIS.end(), arr[i]);
            int idx = it - LIS.begin();
            *it = arr[i];
            order[i] = idx + 1;
        }
    }
 
    int cnt = LIS.size();
 
    printf("%d\n", LIS.size());
 
    for (int i = N - 1; i >= 0; i--) {
        if (order[i] == cnt) {
            ans.push_back(arr[i]);
            cnt--;
        }
    }
 
    for (int i = ans.size() - 1; i >= 0; i--) {
        printf("%d ", ans[i]);
    }
}