BOJ - 가장 긴 증가하는 부분 수열 4(14002)

골드4 : 동적 계획법 문제이다.

생각

전형적인 dp 문제이다. 다만 이 문제는, 경로를 추적해야 한다는 점에서 조금 다르다. 경로를 추적하는 방법으로는 dp를 미리 구해놓고, 이것을 역으로 추적하여 구하는 방법이 가장 간단하다.

정의

dp[i] = i번째 수까지 포함했을 때 가장 긴 증가하는 부분 수열의 길이

점화식

dp[i] = max(dp[i], dp[j] + 1) 단, a[i] > a[j]일 때

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<cmath>
#include<functional>
using namespace std;
 
int N;
int a[1001];
int dp[1001];
vector<int> trace;
 
void tracing(int index){
    trace.push_back(a[index]);
    if (dp[index] == 1) return;
    for (int i = index-1; i > 0; i--) {
        if (dp[index] == dp[i] + 1 && a[index] > a[i]){
            tracing(i);
            break;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }
    fill(dp, dp+N+1, 1);
    for (int i = 1; i <= N; i++) {
        for (int j = i; j > 0; j--) {
            if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
        }
    }
 
    int max = dp[N], maxIdx = N;
    for (int i = N; i > 0; i--) {
        if (max < dp[i]) {
            max = dp[i];
            maxIdx = i;
        }
    }
    tracing(maxIdx);
 
    cout << max << endl;
    for (int i = int(trace.size())-1; i >= 0; i--) {
        cout << trace[i] << ' ';
    }
 
    return 0;
}

Reference

• 백준(14002번) - 가장 긴 증가하는 부분 수열 4