[백준] 14002번 가장 긴 증가하는 부분 수열 4

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

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];

    int answer = 1;
    int maxIdx = 0;
    vector<pair<int, int>> table(n, make_pair(1, -1)); // first: 길이, second: 역추적에 사용
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (table[i].first < table[j].first + 1) {
                    table[i] = make_pair(table[j].first + 1, j);
                }
            }

        }
        if (table[i].first > answer) {
            maxIdx = i; // 역추적에 이용하기 위함
        }
        answer = max(table[i].first, answer);
    }

    cout << answer << "\n";
    stack<int> answerQue;
    stack<int> reverse;
    answerQue.push(maxIdx);
    while (!answerQue.empty()) {
        int idx = answerQue.top();
        answerQue.pop();
        reverse.push(nums[idx]);

        // 만약 길이가 1이면 멈췅
        if (table[idx].first == 1) continue;
        answerQue.push(table[idx].second);
    }

    while (!reverse.empty()) {
        int tmp = reverse.top();
        cout << tmp << " ";
        reverse.pop();
    }

    return 0;
}

 

table 에 길이만 저장하는 것이 아니라 이전 인덱스도 같이 저장하도록 했다. 이전 인덱스를 저장하는 이유는 마지막에 역추적을 하면서 지나온 길을 출력해야 하기 때문이다.

 

maxIdx 에는 가장 긴 부분수열을 이루는 인덱스 값을 넣어놓고 마지막에 이 값을 통해 역추적을 시작하도록 했다. 역추적을 하면 순서가 뒤집혀서 들어가므로 바로 출력하지 않고 스택에 넣은 후 맨 마지막에 차례대로 빼면서 출력했다.