[백준] 11056번 - 두 부분 문자열 [Java][C++]

문제 링크

---

1. 문제 풀이

$A$ 와 $B$ 를 부분 문자열로 갖는 $S$ 의 최소 길이를 찾아야 하는 문제다. 해당 문제는 LCS 알고리즘을 활용하면 해결할 수 있는데 $A$ 와 $B$ 의 LCS의 길이를 $len$ 이라 할 때, $A\ 의\ 길이 + B\ 의\ 길이 - len$ 으로 $S$ 의 길이를 구할 수 있다.

$A$ 와 $B$ 를 합친 문자열을 만들 때, 각각의 문자열의 문자들에 대해 기존 순서를 유지만 하면 어떻게 합치든 합친 문자열은 $A$ 와 $B$ 모두 부분 문자열로 갖는다. 이러면 $A$ 에 $B$ 를 합칠 때, LCS에 해당하는 문자들을 제외한 문자들을 적절하게 합치면 최소한의 문자들로 $S$ 를 만들 수 있다.

---

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();
        int N = str1.length;
        int M = str2.length;

        int[][] dp = new int[1 + N][1 + M];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

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

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;
    cin >> s1 >> s2;

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

    vector<vector<int>> dp(1 + n, vector<int>(1 + m));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << n + m - dp[n][m];
}

---

3. 풀이 정보

1. Bottom-Up dp [Java]

언어	시간	메모리	코드 길이
Java 11	116 ms	18176 KB	767 B

2. Bottom-Up dp [C++]

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

---