[백준/BOJ] 14002 가장 긴 증가하는 부분 수열 4 (c++)

[백준/BOJ] 14002 가장 긴 증가하는 부분 수열 4 (c++)

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

14. Longest Increasing Subsequence (LIS, c++)

14. Longest Increasing Subsequence (LIS, c++)

---

N이 1000이기 때문에 LIS를 구하는 방법 중 하나인, DP를 사용한 O(N^2) 방식으로 해결할 수 있는 문제입니다.

 

d[i] = i번째 숫자를 마지막으로 하는 증가하는 부분 수열의 최대 길이라고 정의 한다면

 

i번째 이전 숫자들 중에서 실제 값이 i번째 수보다 작은 숫자로 만들 수 있었던 최대 길이+1 로 계산할 수 있습니다.

 

이 때, 수열이 어떤 숫자들로 이루어졌는지 찾는 방법은 계산된 DP 값들을 이용해 역으로 추적해볼 수 있습니다.

 

LIS의 길이만큼의 숫자를 뒤에서부터 찾기 시작해서 DP값을 만들 수 있었던 경우(DP값이 하나 작으면서, 숫자도 하나 작은 경우)를 따라가다 보면 어떤 수들로 인해서 계산이 되었는지 알아낼 수 있습니다.

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for(int i=s; i<e; i++)
int N, x;
vector<int> a;

int solve() {
    vector<int> d(N);
    int ans = 0;
    REP(i, 0, N) {
        d[i] = 1;
        REP(j, 0, i) {
            if (a[i] > a[j]) d[i] = max(d[i], d[j]+1);
        }
        ans = max(ans, d[i]);
    }
    vector<int> ret;
    int idx = ans, z = 9999;
    REP(i, 0, N) {
        if(d[N-i-1] == idx && a[N-i-1] < z) {
            ret.push_back(a[N-i-1]);
            z = a[N-i-1];
            idx--;
        }
    }
    cout << ans << "\n";
    REP(i, 0, ans) {
        cout << ret[ans-i-1] << " ";
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    REP(i, 0, N) {
        cin >> x;
        a.push_back(x);
    }
    solve();
    return 0;
}