백준/14003번/가장 긴 증가하는 부분 수열 5/플래티넘5

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

문제 설명

Site: Baekjoon
Number: 14003
Category: Binary Search
Rank: Platinum 5

기존에 가장 긴 증가하는 부분 수열 4와 동일한 소스코드로 문제를 해결하려 한다면 O(N^2)의 시간복잡도가 나와 시간초과가 발생한다.
각 원소별 최대 길이를 모든 원소와 비교하여 구하는 방식

이전에 사용했던 O(NlogN)의 시간 복잡도를 갖는 풀이와 배열을 유도하는 방식을 같이 사용해야 해결이 가능하다.

O(NlogN) 시간 복잡도

lower_bound를 통해 해결한다.

지속적으로 가장 긴 부분 수열의 길이를 저장할 arr 배열을 하나 생성한 후 원소들을 입력받는다.

lower_bound를 사용하여 현재 가장 긴 배열에서 입력 받은 원소가 가능한 가장 큰 길이를 구하고 이를 dp배열에 저장한다.

arr을 그대로 출력하지 않는 이유는 arr은 실질적으로 불가능한 원소가 저장될 수 있기 때문에 가장 긴 길이를 구하는데는 적합하나, 배열 자체를 구하는데에는 적합하지 않다.

dp배열에 각 원소별 위치할 수 있는 최대 길이를 저장하고 이를 줄여가며 stack에 저장하면 실질적으로 가능한 배열을 구하여 출력할 수 있다.

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

int dp[1000001];
int nums[1000001];
int arr[1000001];

int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);

    int N, length = 0;
    cin >> N;

    for (int i = 1; i < N + 1; i++)
    {
        cin >> nums[i];

        auto iter = lower_bound(arr, arr + length, nums[i]);
        *iter = nums[i];

        if (iter == arr + length)
        {
            length++;
        }
        dp[i] = iter - arr + 1;
    }

    stack<int> s;
    cout << length << endl;

    for (int i = N; i > 0; i--)
    {
        if (length == dp[i])
        {
            s.push(nums[i]);
            length--;
        }
    }
    while (!s.empty())
    {
        cout << s.top() << ' ';
        s.pop();
    }


    return 0;
}