[BOJ 14003번/C++] 가장 긴 증가하는 부분 수열 5

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

가장 긴 증가하는 부분 수열 5

풀이

가장 긴 증가하는 부분 수열 문제들의 최종 보스(?)인 5번째 문제이다. O(nlogn)을 강요하는 문제이면서, 그 수열이 무엇인지도 출력해야하는 문제였다. 기존에, nlogn 풀이였던 코드를 먼저 가져와보자.

#include <iostream>
#include <vector>
#include <algorithm>

#define endl '\n'

using namespace std;

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    vector<int> A;
    int a;
    for (int i = 0; i < N; i++) {
        cin >> a;
        A.push_back(a);
    }

    vector<int> LIS;
    LIS.push_back(A[0]);
    int len = 0;
    for (int i = 1; i < N; i++) {
        if (A[i] > LIS[len]) {
            LIS.push_back(A[i]);
            len++;
        }
        else {
            vector<int>::iterator idx = lower_bound(LIS.begin(), LIS.end(), A[i]);
            *idx = A[i];
        }
    }

    cout << len + 1 << endl;

    return 0;
}

여기서 LIS 배열에 있는 값을 불러와 출력하면 되겠다! 하고 간단히 풀릴 문제였다면 좋았겠지만 그렇지 않은 문제이다. (실제로 그랬더니 1%조차 안오르고 바로 틀렸습니다가 떠버리더라.)

 

그래서 여기서 이용할 방법은, LIS 배열에 저장될 수가 LIS 배열에서 몇 번 인덱스에 저장되는지를 같이 기록해두는 것이다.

A = { 10, 30, 20, 50, 40 } 을 예로 들면, 아래 과정을 거친다.

 

첫 번째,

LIS = { 10 }

IDX = { 0 }

LIS 길이 = 1

 

두 번째,

LIS = { 10, 30 }

IDX = { 0, 1 }

LIS 길이 = 2

 

세 번째,

LIS = { 20, 30 }

IDX = { 0, 1, 0 }

LIS 길이 = 2

 

네 번째,

LIS = { 20, 30, 50 }

IDX = { 0, 1, 0, 2 }

LIS 길이 = 3

 

마지막,

LIS = { 20, 30, 40 }

IDX = { 0, 1, 0, 2, 2 }

LIS 길이 = 3

 

가장 긴 증가하는 부분 수열을 구해보자. IDX 배열에서 가장 큰 값은 2이다. 2가 두개지만, 가장 뒤에 있는 것을 선택하도록 하겠다. 그러면 다섯번째 원소인 40이 가장 긴 증가하는 부분 수열에서 가장 큰 값이 된다.

1씩 줄여가면서 원소들을 구해보면, 각각 40, 20, 10이 된다. 출력은 이를 역순으로 한 { 10, 20, 40 } 이 구하고자 하는 답이 된다.

#include <iostream>
#include <vector>
#include <algorithm>

#define endl '\n'

using namespace std;

int LIS[1000001]; // 가장 긴 증가하는 부분 수열의 길이를 구하기 위한 배열..
int IDX[1000001]; // 원소들이 LIS 배열에 저장될 때 LIS 배열의 몇 번째 인덱스에 저장되는지 기억하기 위한 배열..

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    vector<int> A;
    int a;
    for (int i = 0; i < N; i++) {
        cin >> a;
        A.push_back(a);
    }

    LIS[0] = A[0];
    IDX[0] = 0;
    int len = 1;
    for (int i = 1; i < N; i++) {
        if (A[i] > LIS[len - 1]) {
            LIS[len] = A[i];
            IDX[i] = len;
            len++;
        }
        else {
            int* idx = lower_bound(LIS, LIS + len, A[i]);
            *idx = A[i];
            IDX[i] = idx - LIS;
        }
    }

    int max_len = *max_element(IDX, IDX + N) + 1;
    cout << max_len << endl;
    vector<int> answer;
    for (int i = N - 1; i >= 0 && max_len > 0; i--) {
        if (IDX[i] == max_len - 1) {
            answer.push_back(A[i]);
            max_len--;
        }
    }

    for (int i = answer.size() - 1; i >= 0; i--) {
        cout << answer[i] << " ";
    }

    return 0;
}