[Algorithm]Baekjoon 14003 :: 가장 긴 증가하는 부분수열 5

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

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

 
 
using namespace std;
 
int n;
int arr[1000001] = { 0 };
vector<int> lis;
vector<int> indices;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    lis.push_back(arr[0]);
    indices.push_back(0);
 
    for (int i = 1; i < n; ++i)
    {
        int index = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
 
        if (index == lis.size()) // 오름차순 형성되면
        {
            lis.push_back(arr[i]);
        }
        else // 형성안되면
        {
            lis[index] = arr[i];
        }
 
        indices.push_back(index);
    }
 
    cout << lis.size() << endl;
    vector<int> answer;
    
    int index = lis.size() - 1;
    for (int i = n - 1; i >= 0; --i)
    {
        if (indices[i] == index)
        {
            answer.push_back(arr[i]);
            --index;
        }
    }
 
    for (int i = answer.size() - 1; i >= 0; --i)
    {
        printf("%d ", answer[i]);
    }
}

 

동일한 유형을 최근에 풀었었다.

그래서 그때 내가 제대로 이해하고 기억하고있는지 검증하기 위해 풀었는데, 다행히 그때 잘 숙지했었나보다.

lis의 크기뿐만 아니라 원소까지 전부 구해야하는 문제이기 때문에, lis에 업데이트했던 원소들의 인덱스를 전부 따로 저장하고있어야 한다. 

 

크기만 구하는 문제면 41번째라인에서 끝난다.