[BOJ] 1958번 - LCS 3

백준 1958번 - LCS3 

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	4098	1978	1537	49.629%

문제

문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.

이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

입력

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다)

출력

첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.

예제 입력 1

abcdefghijklmn
bdefg
efg

예제 출력 1

3

출처

링크

알고리즘 분류

• DP
• 문자열

접근 방법

LCS 알고리즘을 잘 이해하고 있어야만 풀 수 있는 응용문제였다.

문자열 X,Y,Z 를 다음과 같은 부분문제로 쪼개보자.

 

${X_i = x_1 x_2 x_3 ... x_i}$ 까지의 접두사 배열

${Y_j = y_1 y_2 y_3 ... y_j}$ 까지의 접두사 배열

${Z_k = z_1 z_2 z_3 ... z_k}$ 까지의 접두사 배열

 

부분 문제와의 연관성을 찾기 위해 다음과 같이 DP table 을 정의해보자.

  ${DP[i][j][k] = X_i Y_j Z_k}$ 일 때 세 문자열의 최장공통부분수열의 길이. 

 

위와 같이 DP table을 정의한다면, 부분 문제와의 연관성을 찾아보자.

DP[i][j][k] 가 증가하는 경우는 오직 ${x_i == y_j == z_k}$ 일 때 뿐이다.

즉, ${x_i == y_j == z_k}$ 일 때 ${x_i , y_j , z_k}$는 LCS에 포함되는 값이므로

이전 까지 구해 놓은 DP[i-1][j-1][k-1] 값에 +1을 한 다음 값을 메모이제이션 한다.

 

그 외 경우는 ${x_i \neq y_j \quad 또는 \quad y_j \neq z_k  \quad또는 \quad  x_i \neq z_k}$ 가 될 수 있겠다.

이 경우에는 다음 연산에서 필요한 DP table을 유지하기 위해 현재 까지의 LCS최대 값을 유지한다.

 

1. $X_i$ 까지의 LCS를 유지한다. -> { $max( DP[i][j-1][k-1], DP[i][j-1][k], DP[i][j][k-1] )$ }

$Y_j$ 와 $Z_k$도 동일한 방식으로 DP table을 유지시켜주면 된다.

 

점화식은 다음과 같다.

 

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
string a,b,c;
int dp[101][101][101];
int max(int a, int b, int c){
    int ret = a;
    ret = ( ret < b ) ? b : ret;
    ret = ( ret < c ) ? c : ret;
    return ret;
}
void init(){
    for(int i=0; i<b.size(); i++){
        for(int j=0; j<c.size(); j++)
            dp[0][i][j] = 0;
    }
    for(int i=0; i<a.size(); i++){
        for(int j=0; j<c.size(); j++)
            dp[i][0][j] = 0;
    }
    for(int i=0; i<a.size(); i++){
        for(int j=0; j<c.size(); j++)
            dp[i][j][0] = 0;
    }
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> a >> b >> c;
    a = '\0' + a, b = '\0' + b, c = '\0' + c;

    init();

    for(int i=1; i<a.size(); i++){
        for(int j=1; j<b.size(); j++){
            for(int k=1; k<c.size(); k++){
                if( a[i] == b[j] && b[j] == c[k] && a[i] == c[k] )
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                else{
                    int ret1 = max(dp[i][j-1][k-1], dp[i][j-1][k], dp[i][j][k-1] );
                    int ret2 = max(dp[i-1][j][k-1], dp[i-1][j][k], dp[i][j][k-1] );
                    int ret3 = max(dp[i-1][j-1][k], dp[i-1][j][k], dp[i][j-1][k] );
                    dp[i][j][k] = max(ret1,ret2,ret3);
                }
            }
        }
    }

    cout << dp[a.size()-1][b.size()-1][c.size()-1];


    return 0;
}