이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 111 번째 글 입니다.
목차
골드5 : 동적계획법 문제이다.
풀이
dp[i][j] = (i, j)번째 수열의 원소를 포함했을 때, 가지는 최장 수열의 길이
dp[i][j] = max(dp[i-1][j-1]~dp[0][0])
하지만 실제 구현을 이런식으로 하게 되면, $O(n^4)$ 로 시간 초과가 날 것이다. 따라서 i번째 원소를 업데이트 한 이후에, dp의 값이 사용이 되는지 확인할 필요가 있다.
무조건적으로 이전 원소(i)를 본 뒤에는 값이 큰 상태로 유지되며, 다음 상태의 최장 길이는 이 값으로부터 도출될 수 밖에 없다. 따라서 최적화가 가능하다.
Code
#include <iostream>
#include <string>
using namespace std;
int dp[1001] = {0,};
int main(){
string a, b;
cin >> a >> b;
for (int i = 0; i < a.size(); i++) {
int temp[1001];
for (int j = 0; j < b.size(); j++) {
temp[j] = dp[j];
}
for (int j = 0; j < b.size(); j++) {
if (a[i] == b[j]) {
int maxvalue = 0;
for (int k = 0; k < j; k++) {
if (temp[k] > maxvalue) {
maxvalue = temp[k];
}
}
dp[j] = maxvalue+1;
}
}
// for (int k = 0; k < b.size(); k++) {
// cout << dp[k] << " ";
// }
// cout << '\n';
}
int ans = 0;
for (int i = 0; i < b.size(); i++) {
if (ans < dp[i]) {
ans = dp[i];
}
}
cout << ans << '\n';
return 0;
}