이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 40 번째 글 입니다.
목차
골드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;
}