[boj] 백준 9251 LCS - 동적프로그래밍

[문제]

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

9251번: LCS

 

[풀이]

최장 공통 부분 수열이란 연속되어 있지 않아도 되는 공통된 문자열을 의미한다. 예를 들어, ACAYKP와 CAPCAK의 경우 ACAK가 연속되지는 않아도 공통된 문자열로 포함되어 있는 LCS다.

LCS는 문자열 a,b가 있다고 했을 때, a를 기준으로 b 문자열을 비교해 나가면서 같은 문자인 경우 카운트해줘야 하므로 이전까지의 LCS + 1을, 다른 문자인 경우 이전까지의 LCS에서 각각 다른 문자를 넣었을 때의 더 큰 값으로 LCS 값을 갱신해주면 되고, 이를 저장하기 위해 dp 배열을 사용한다.

표로 나타내면 다음과 같다.

 

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

예를 들어, 다음 표에서 빨간색 글씨로 나타낸 부분은 AC와 CAPC의 LCS 값이다. C라는 같은 문자가 나왔으므로 이전 LCS값은 A와 CAP를 비교했을 때의 LCS값(표 상에서 왼쪽 위 대각선 값)인 1에 +1을 해서 2가 된 것이고 AC가 겹치는 것을 의미한다. 다음과 같이 공통된 문자가 나오면 그 문자가 겹치기 이전의 LCS값인 dp[i-1][j-1]에 1을 더해주는 것으로 생각할 수 있다.

반면, 파란색으로 표시한 부분은 ACA와 CAP의 LCS 값이다. A와 P는 같은 문자가 아니므로 이전 LCS값+1로 갱신해주면 안된다. 이때는 이전까지의 LCS에서 각각 다른 문자를 넣었을 때 더 큰 값으로 갱신해줘야 한다. 여기서는 AC와 CA에 대해서 CA에 P를 추가한 AC, CAP의 LCS는 1, AC에 A를 추가한 ACA, CA의 LCS는 2이므로 2로 LCS 값을 갱신해준 것을 알 수 있다. 따라서 dp[i][j]는 dp[i-1][j]와 dp[i][j-1] 중에서 더 큰 값을 넣어주면 된다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace::std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s1, s2;
    cin >> s1 >> s2;

    int dp[1001][1001];

    for(int i=1; i<=s1.length(); i++){
        for(int j=1; j<=s2.length() ; j++){
            if(s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    cout << dp[s1.length()][s2.length()];

}