백준 9251 / C++

https://www.acmicpc.net/problem/9251

9251번: LCS

 

[ 풀이 ] 

 

dp[i][j]를 문자열 1개를 i번을 볼 것이고 , 나머지를 j번을 보려고 할 때  지금까지 겹치는 것의 개수라고 하자. 

겹치지 않으면 한 문자열을 한칸 이동시켜준다. 

겹치면 두 문자열을 모두 한칸 이동시켜준다. 

dp[i][j]=max(dp[i+1][j], dp[i][j+1], if a[i]=b[j],  dp[i+1][j+1]+1) 로 쓸 수 있다.

 

[ 코드 ] 

 

#include <bits/stdc++.h>
using namespace std;
int n, dp[1001][1001];
string a, b;
 
int go(int i, int j) {
    if (i == a.size() || j == b.size()) return 0;
    int& ret = dp[i][j];
    if (ret != -1) return ret;
    ret = -1e9;
    ret = max(go(i + 1, j), go(i, j + 1));
    if (a[i] == b[j]) ret = max(ret, go(i + 1, j + 1) + 1);
    return ret;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> a >> b;
    memset(dp, -1, sizeof(dp));
    cout << go(0, 0) << '\n';
}