[백준] 1958번 - LCS 3 [Java][C++]

문제 링크

---

1. 문제 풀이

세 문자열의 LCS 문제로 두 문자열의 LCS는 2차원 dp 테이블을 활용해서 해결하듯이, 3차원 dp 테이블을 활용하면 된다.

문자열 $A$, $B$, $C$ 의 LCS를 구하는 dp 점화식은 아래와 같다.

\[dp[i][j][k] = \begin{cases} 0, & \text{if } i = 0 \text{ or } j = 0 \text{ or } k = 0 \\\\ dp[i-1][j-1][k-1] + 1, & \text{if } A[i] = B[j] = C[k] \\\\ \max \big( dp[i-1][j][k],\ dp[i][j-1][k],\ dp[i][j][k-1] \big), & \text{otherwise} \end{cases}\]

---

2. 코드

1. Bottom-Up dp [Java]

dp 테이블 앞에 패딩을 한 칸씩 줬다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        char[] str3 = br.readLine().toCharArray();
        int L = str1.length;
        int M = str2.length;
        int N = str3.length;

        int[][][] dp = new int[1 + L][1 + M][1 + N];
        for (int i = 1; i <= L; i++) {
            for (int j = 1; j <= M; j++) {
                for (int k = 1; k <= N; 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] = Math.max(dp[i - 1][j][k], Math.max(dp[i][j - 1][k], dp[i][j][k - 1]));
                    }
                }
            }
        }

        System.out.println(dp[L][M][N]);
    }
}

2. Bottom-Up dp [C++]

dp 테이블 앞에 패딩을 한 칸씩 줬다.

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

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

    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;

    int l = s1.size();
    int m = s2.size();
    int n = s3.size();

    vector<vector<vector<int>>> dp(1 + l, vector<vector<int>>(1 + m, vector<int>(1 + n)));
    for (int i = 1; i <= l; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 1; k <= n; k++) {
                if (s1[i - 1] == s2[j - 1] && s2[j - 1] == s3[k - 1]) {
                    dp[i][j][k] = dp[i - 1][j - 1][k - 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[l][m][n];
}

---

3. 풀이 정보

1. Bottom-Up dp [Java]

언어	시간	메모리	코드 길이
Java 11	148 ms	19732 KB	1012 B

2. Bottom-Up dp [C++]

언어	시간	메모리	코드 길이
C++ 17	4 ms	6512 KB	773 B

---