LCS C++ - 백준 9251

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

LCS(Longest Common Subsequence) 최장공통부분수열 문제.

LCS 알고리즘

최장공통부분수열은 어떻게 구할까?

배우지 않았을때는 접근하기가 매우 어려웠다.

LCS는 DP로 해결할 수 있다.

먼저 길이가 $7$인 문자열 $S_7$ 길이가 $9$인 문자열 $T_9$이 있다고 하자.

$S:ABCBDDA$
$T:BCDABDBCD$

$S$의 길이가 $i$인 부분 문자열과, $T$의 길이가 $j$인 부분 문자열의

최장공통부분수열을 $LCS(i,j)$로 표현하겠다.

두 문자열의 부분 문자열 $S_i$ $T_j$의 마지막 부분 문자열을 살펴보자

만약 $i=4, j=7$이라고 할때 마지막 부분 문자열은 $B$로 같다.

부분 문자열이 $B$로 같으므로 $LCS(4,7)$은 $LCS(3,6)+1$이 될 것이다.

이번에는 다른 경우를 살펴보자.

만약 $i=4, j=9$ 일때는 부분 문자열이 $B,D$로 다르다.

이때 $LCS(4,9)$는 여태까지의 부분문자열 중 제일 긴 것이다.

따라서 $LCS(4,9)=max(LCS(4,8),LCS(3,9))$이다.

이를 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

string a,b;
int dp[1001][1001];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> a >> b;
    memset(dp,0,sizeof(dp));
    for(int i=0;i<a.length();i++) for(int j=0;j<b.length();j++){
        if(a[i]==b[j]) dp[i+1][j+1]=dp[i][j]+1;
        else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
    }
    cout << dp[a.length()][b.length()];
    return 0;
}