[LCS] 백준 1958 :: LCS 3

LCS 3 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2966	1390	1088	48.615%

문제

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

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

입력

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

출력

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

예제 입력 1 

abcdefghijklmn
bdefg
efg

예제 출력 1 

3

     

 문제 풀이

1차 풀이 (  6012 KB,  24 ms)

Top-down 방식의 LCS 알고리즘 변형.

A와 B의 LCS를 구할 때에는,

A 또는 B 중에서 하나 선택하여, 인덱스를 1 전진시켰다.

마찬가지로,

A와 B와 C의 LCS를 구할 때에는,

A 또는 B 또는 C 중에서 하나 선택하여, 인덱스를 1 전진시킨다.

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

const int SIZE = 100;
int cache[SIZE+1][SIZE+1][SIZE+1];
char A[SIZE+1];
char B[SIZE+1];
char C[SIZE+1];

int LCS(int i, int j, int k){
        //! case condition.
        if(i==0 || j==0 || k==0) return 0;

        //! memoization.
        if(cache[i][j][k] != -1) return cache[i][j][k];

        //! solving.
        if(A[i]==B[j] && B[j]==C[k]) {
                cache[i][j][k] = LCS(i-1, j-1, k-1)+1;
        }
        else {
                int val = 0;
                val = max(val, LCS(i-1, j, k));
                val = max(val, LCS(i, j-1, k));
                val = max(val, LCS(i, j, k-1));
                cache[i][j][k] = val;
        }
        return cache[i][j][k];
}

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

        memset(cache, -1, sizeof cache);
        cin >> (A+1);
        cin >> (B+1);
        cin >> (C+1);

        cout << LCS(strlen(A+1), strlen(B+1), strlen(C+1));
}

2차 풀이 (  6012 KB,  4 ms)

Bottom-up 방식의 LCS 알고리즘 변형.

A와 B의 LCS를 구할 때에는,

A에서 1 감소시킨 것과,

B에서 1 감소시킨 것 중, 큰 것을 골랐다.

마찬가지로,

A와 B와 C의 LCS를 구할 때에는,

A 에서 1 감소시킨 것 과,

B 에서 1 감소시킨 것 과,

C 에서 1 감소시킨 것 중, 큰 것을 고른다.

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

const int SIZE = 100;
int cache[SIZE+1][SIZE+1][SIZE+1];
char A[SIZE+1];
char B[SIZE+1];
char C[SIZE+1];

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

        memset(cache, 0, sizeof cache);
        cin >> (A+1);
        cin >> (B+1);
        cin >> (C+1);

        for(auto i=1; i<=strlen(A+1); i++){
                for(auto j=1; j<=strlen(B+1); j++){
                        for(auto k=1; k<=strlen(C+1); k++){
                                if(A[i]==B[j] && B[j]==C[k]) {
                                        cache[i][j][k] = cache[i-1][j-1][k-1]+1;
                                }
                                else {
                                        int val = 0;
                                        val = max(val, cache[i-1][j][k]);
                                        val = max(val, cache[i][j-1][k]);
                                        val = max(val, cache[i][j][k-1]);
                                        cache[i][j][k] = val;
                                }
                        }
                }
        }
        cout << cache[strlen(A+1)][strlen(B+1)][strlen(C+1)];
}