[DP] 1958번 LCS3

1958번 LCS 3

 

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

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

abcdefghijklmn
bdefg
efg

 

예제 출력

3

 

해결방법

LCS(Longest Common Subsequence) 를 적용한 DP 문제이다

 

 

⭐️ 솔루션 ⭐️

LCS 문제 에서 2가지 문자열에서 3가지 문자열로 확장된 문제이다

해결방법은 간단하지만 이 솔루션을 생각하기는 너무 어려웠다... ㅠㅠ

 

문제를 처음 보고 든 생각은 Str1 과 Str2 를 비교하여 LCS 를 구한 뒤, Str3 와 LCS 를 한번더 구하면 되지 않을까? 라는 생각이었다

하지만 이는 반례가 존재했다

Str1 : dababcf
Str2 : ababdef
Str3 : df

LCS(A,B) : ababf
LCS(LCS(A,B),C) : f
LCS(A,B,C) : df

 

이를 해결하기 위해 구글링을 하다가 이는 단순히 차원을 하나 늘려서 해결할 수 있다는 솔루션을 발견했다

또한 n의 조건이 n ≤ 100 이므로 3차원으로 해결해도 시간초과가 발생하지 않았다

 

 

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

string s1,s2,s3;
int l1,l2,l3;
int d[101][101][101];

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> s1 >> s2 >> s3;
    
    int l1 = (int) s1.size();
    int l2 = (int) s2.size();
    int l3 = (int) s3.size();
    
    for(int i=1; i<=l1; i++){
        for(int j=1; j<=l2; j++){
            for(int k=1; k<=l3; k++){
                if(s1[i-1]==s2[j-1] && s2[j-1]==s3[k-1]){
                    d[i][j][k] = d[i-1][j-1][k-1] + 1;
                }else{
                    d[i][j][k] = max(d[i-1][j][k],max(d[i][j-1][k],d[i][j][k-1]));
                }
            }
        }
    }
    
    cout << d[l1][l2][l3] << "\n";
    
    return 0;
}