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

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

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

 

 

[ 문제풀이 ]

 

lower_bound를 잘 활용하고 각 수의 index를 잘 저장해주면 쉽게 풀 수 있는 문제입니다.

 

먼저 각 수의 index를 저장할 index배열을 만듭니다. 그리고 각 수가 LIS의 몇 번째 인덱스에 있는지 계속 체크해주면서 index 배열에 저장해줍니다.

 

10 20 10 30 20 50

 

위의 수열을 예로 들면 

 

 

그리고 나서 index배열의 끝에서부터 값이 큰 수부터 차례로 ans 배열에 저장한 후 ans 배열을 출력해주면 됩니다.

 

 

[ 소스 코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N;
vector<int> lis;
vector<int> ans;
int arr[1000001];        //전체 배열
int index[1000001];        //lis 좌표를 저장하기 위한 배열
 
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        if (i == 0) {
            lis.push_back(arr[i]);
            index[i] = lis.size();        //lis의 몇번 째에 있는지 저장
        }
        else {
            if (*lis.rbegin() < arr[i]) {
                lis.push_back( arr[i] );
                index[i] = lis.size();    //lis의 몇번 째에 있는지 저장
            }
            else {
                auto idx = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
                lis[idx] = arr[i];        
                index[i] = idx + 1;        //lis의 몇번 째에 있는지 저장
            }
        }
    }
 
    int cnt = lis.size();
 
    for (int i = N - 1; i >= 0; i--) {    //반대부터 index를 1씩 줄여가며 순서대로 저장
        if (index[i] == cnt) {
            ans.push_back(arr[i]);
            cnt--;
        }
 
        if (cnt == 0) break;
    }
 
    cout << lis.size() << endl;
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << " ";
    }
}