[BOJ C++] 백준 1958번: LCS 3

 📚 문제

[BOJ C++] 백준 1958번: LCS 3
https://www.acmicpc.net/problem/1958

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 DP를 사용하여 해결할 수 있다. 이 LCS 3 문제는 앞서 해결했던 LCS 문제를 바탕으로 해결할 수 있다. 자세한 설명은 아래 링크를 참조하자.
• [이론] 최장 공통 부분 수열 (LCS, Longest Common Subsequence)
• [BOJ C++] 백준 9251번: LCS
• 처음에는 두 문자열을 먼저 비교하여 LCS를 찾고, 찾은 LCS와 세 번째 문자열의 LCS를 찾는 방법으로 해결할 수 있을 것이라 생각했다. 그러나 이 문제에는 치명적인 문제점이 있어 올바른 정답을 구할 수 없다. 백준 질문 게시판에 올라와 있는 반례를 활용하였다.
• 예를 들어 세 문자열이 "dababcf", "ababdef", "df"라고 하자. "dababcf"와 "ababdef"의 LCS를 먼저 구해보면, "ababf"임을 알 수 있다. 그리고 구한 문자열과 "df"의 LCS를 구한 결과는 "f"이다. LCS는 말 그대로 가장 긴 공통 문자열을 찾는 문제이므로 공통된 문자가 있더라도 LCS 결과에서는 생략될 가능성이 있다. 따라서 이 문제는 LCS를 두 번 수행하는 방식이 아닌, 3차원 배열로 LCS를 한 번에 구하는 방법을 사용하여 해결해야 한다.
• 방식은 2차원 배열을 사용했을 때와 같다. 이중 for문을 삼중 for문으로 바꾸면 되고, 세 문자(str1[i], str2[j], str3[k])가 모두 같을 때 이전 값에서 +1을 수행한다.
  dp[i][j][k] = dp[i-1][j-1][k-1] + 1
• 그렇지 않은 경우에는 str1[i]를 고려하지 않은 경우(str1[i-1]까지 고려), str2[j]를 고려하지 않은 경우(str2[j-1]까지 고려), str3[k]를 고려하지 않은 경우(str3[k-1]까지 고려) 중 가장 큰 값을 저장한다.
  dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
  C++에서는 max 함수에 인자를 2개까지만 넣을 수 있으므로 앞의 두 값을 비교하여 dp[i][j][k]에 저장하고, 저장된 값과 세번째 값을 비교하는 방식으로 코드를 작성하였다.

---

 ⌨️ C++ 코드

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string str1, str2, str3;
    cin >> str1 >> str2 >> str3;
    int l1 = str1.size(), l2 = str2.size(), l3 = str3.size();
    vector<vector<vector<int>>> dp(l1 + 1, vector<vector<int>>(l2 + 1, vector<int>(l3 + 1)));

    for (int i = 1; i <= l1; i++) {
        for (int j = 1; j <= l2; j++) {
            for (int k = 1; k <= l3; k++) {
                if (str1[i - 1] == str2[j - 1] && str2[j - 1] == str3[k - 1])
                    dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
                else {
                    dp[i][j][k] = max(dp[i][j - 1][k], dp[i][j][k - 1]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]);
                }
            }
        }
    }
    cout << dp[l1][l2][l3];
}