[C++] 백준 1958번 LCS 3 풀이

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

1958번: LCS 3

 

문제

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

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

 

풀이

우리가 문자열 2개의 LCS를 구할 때 2차원 dp배열을 이용했다. 이 문제는 정말 단순하게 dp배열을 3차원으로만 늘리면 쉽게 풀린다. 3개의 문자열 s1, s2, s3가 있을 때 각각 i, j, k번 문자가 같을 경우 i, j, k번 이전의 문자열까지 중에 가장 큰 공통 부분 문자열의 크기에 1을 더한다. 그렇지 않을 경우 각각 i-1, j-1, k-1번까지의 공통 부분 문자열의 최대 크기를 저장한다. 코드로 나타내면 다음과 같다.

 

소스 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int MN = 101;

int dp[MN][MN][MN];

int max(int a, int b, int c) { //인자 3개짜리 최대값 함수
    return max(max(a, b), c);
}

int main() {
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3; //3개의 문자열 입력
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    s3 = ' ' + s3;
    for(int i = 1; i < s1.size(); i++) {
        for(int j = 1; j < s2.size(); j++) {
            for(int k = 1; k < s3.size(); k++) {
                if(s1[i] == s2[j] && s2[j] == s3[k]) { //3개 문자가 모두 같은 경우
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1; //이전 공통 부분 문자열 크기에 1을 더함
                }
                else { //같지 않은 경우
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]); //지금까지의 최대값 저장
                }
            }
        }
    }
    cout << dp[s1.size()-1][s2.size()-1][s3.size()-1];
}

 

채점 결과