[C++, python] BOJ, 백준 1958 - LCS 3

문제 링크

1958번: LCS 3

문제 풀이

이 문제는 세 문자열 사이에 공통적으로 존재하는 부분 문자열 중, 가장 길이가 긴 문자열을 찾는 문제이다.

이 문제를 풀기 위해서는 LCS 알고리즘을 사용해야 한다.

이 문제는 공통 부분 문자열과 비슷하지만 약간 다르다.

• 문자열이 2개가 아닌 3개라는 점
• 가장 길이가 긴 연속하는 부분 문자열(STRING)이 아닌 연속하지 않은 부분 문자열(SUBSEQUENCE)

이 두개의 특징때문에 문제 풀이가 약간 달라진다. 연속하는 부분 문자열을 찾았을 때는 문자열1의 i번째와 문자열2의 j번째의 값이 바로 직전 값인 i-1, j-1의 값만 반영했었다. 하지만 연속하지 않은 부분 문자열은 지금까지의 누적 값을 받아와야하기 때문에, i, j번째의 왼쪽값 혹은 윗값 중 최댓값을 반영한다.

따라서 3개의 문자열일 경우는 다음과 같이 반영할 수 있다.

LCS배열은 LCS[문자열1의 길이][문자열2의 길이][문자열3의 길이]인 3차원 배열을 가진다. 문자열1은 i번째, 문자열2는 j번째, 문자열3은 k번째 문자라고 한다면,

• [ i-1 == j-1 == k-1 ] 일 경우, LCS[i][j][k] = LCS[i - 1][j - 1][k - 1] + 1
• 위 조건이 맞지 않을 경우, LCS[i][j][k] = max(LCS[i - 1][j][k], LCS[i][j - 1][k], LCS[i][j][k - 1])

로 규칙을 찾을 수 있다.

정답 코드

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define ll long long
string a, b, c;
int LCS[101][101][101];

int main() {
    fast;
    cin >> a >> b >> c;
    int answer = 0;
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            for (int k = 1; k <= c.length(); k++) {
                if (a[i - 1] == b[j - 1] && a[i - 1] == c[k - 1])
                    LCS[i][j][k] = LCS[i - 1][j - 1][k - 1] + 1;
                else LCS[i][j][k] = max(max(LCS[i - 1][j][k], LCS[i][j - 1][k]), LCS[i][j][k - 1]);
            }
        }
    }
    cout << LCS[a.length()][b.length()][c.length()];
    return 0;
}

python

a = input()
b = input()
c = input()
LCS = [[[0] * 101 for _ in range(101)] for _ in range(101)]
for i in range(1, len(a) + 1) :
    for j in range(1, len(b) + 1) :
        for k in range(1, len(c) + 1) :
            if (a[i - 1] == b[j - 1] and a[i - 1] == c[k - 1]) :
                LCS[i][j][k] = LCS[i - 1][j - 1][k - 1] + 1
            else :
                LCS[i][j][k] = max(LCS[i - 1][j][k], LCS[i][j - 1][k], LCS[i][j][k - 1])
print(LCS[len(a)][len(b)][len(c)])