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

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

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

lis 알고리즘의 가장 큰 문제점은 길이는 정확하게 알수 있는데,

그 값을 찾아가는 과정을 정확하게 알아내지 못한다는 점이다.

같은 수가 나오거나, 길이는 같은데 다른 값이 갱신된다던가 하는 문제이다.

이 때는, lis배열 뿐만아니라 스택과 값을 저장할 벡터를 추가하여 문제를 해결한다.

벡터는 pair로 입력받아, lis에 추가되는 인덱스와 값을 동시에 넣어준다.

lis의 길이를 찾는 과정이 끝나면,

벡터의 끝부분부터 pair의 lis가 같을때 스택에 추가해주고 erase;

그 다음, 스택에 있는 값을 순서대로 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
 
int lis, n;
int arr[1001];
int Lis[1001];
vector<pair<int, int> > pii;
stack<int> s;
 
int lower_bound(int start, int end, int target)
{
    int mid;
    while (end - start > 0)
    {
        mid = (start + end) / 2;
 
        if (Lis[mid] < target)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    Lis[0] = arr[0];
    pii.push_back(make_pair(0, Lis[0]));
 
    for (int i = 1; i < n; i++) {
        if (Lis[lis] < arr[i])
        {
            Lis[lis + 1] = arr[i];
            lis++;
 
            pii.push_back(make_pair(lis, arr[i]));
        }
        else
        {
            int ans = lower_bound(0, lis, arr[i]);
            Lis[ans - 1] = arr[i];
 
            pii.push_back(make_pair(ans - 1, arr[i]));
        }
    }
 
    printf("%d\n", lis + 1);
 
    for (int i = pii.size(); i >= 0; i--) {
        if (pii[i - 1].first == lis) {
            s.push(pii[i - 1].second);
            lis--;
        }
        if (lis == -1) break;
    }
 
    while (!s.empty()) {
        printf("%d ", s.top()), s.pop();
    }
 
    return 0;
}

복습 20.02.09