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

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

#include <iostream>
#include <cstdio>
#include <stack>
#include<algorithm>
using namespace std;
 
typedef pair<int, int> pii;
 
int N;
int lis[1000001];
int S[1000001];
pii arr[1000001];
 
 
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> S[i];
    
    int plis = 0;
    int pArr = 1;
    lis[0] = S[0];
    arr[0].first = 0;
    arr[0].second = S[0];
    //arr[i].first는 실제 그 값이 들어갈 수 있는 위치
    //arr[i].second는 실제 그 값을 의미
    while (pArr < N) {
        if (lis[plis] < S[pArr]) {
            lis[++plis] = S[pArr];
            arr[pArr].first = plis;
            arr[pArr].second = S[pArr];
        }
        else {    
            int pos = lower_bound(lis, lis + plis, S[pArr]) - lis ;//S[pArr]보다 큰숫자들중 제일 작은위치반환.
            lis[pos] = S[pArr];
            arr[pArr].first = pos;
            arr[pArr].second = S[pArr];
        }
        pArr++;
    }
    cout << plis + 1 << endl;
    stack<int> s;
    int t = plis;
    for (int k = N - 1; k >= 0; k--) {
        if (t == arr[k].first) {
            s.push(arr[k].second);
            t--;
        }
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    return 0;
}

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

생각보다 어려운 문제였습니다. 

문제 풀 때 이 블로그 해설을 참고해서 풀었습니다. https://www.crocus.co.kr/681 (감사합니다 ㅎㅎ...)

이 문제와 동일하게 배열크기만 다른 백준 14002번도 이 코드로 해결이 가능합니다.