[BOJ C++] 백준 11056번: 두 부분 문자열

 📚 문제

[BOJ C++] 백준 11056번: 두 부분 문자열
https://www.acmicpc.net/problem/11056

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 이 문제는 앞서 풀었던 LCS(Longest Common Subsequence) 문제를 응용하면 해겨할 수 있다. 부분 수열(Subsequence)와 부분 문자열(Substring)의 차이는 연속성에 있다.
• 그러나 이 문제에서 의미하는 부분 문자열은 Substring이 아닌 Subsequence를 의미한다. 이는 문제의 설명에서 A = "beakjoon", B = "hongjun"의 부분 문자열이 "beakhongjouon"이라고 한 설명을 통해 알 수 있다. 우리가 알고 있는 연속하는 부분 문자열을 의미했다면 "beakjoonhonghun"과 같은 형식이 되어야 하기 때문이다.
• 앞선 문제들과 달리 두 문자열의 가장 긴 부분 공통 수열이 아닌 두 문자열을 포함하는 가장 짧은 문자열의 길이를 구하는 문제이다. 두 문자열을 부분 수열로 갖는 문자열은 두 문자열을 나란히 연결한 형태일 것이다. 그러나 가장 짧은 문자열을 찾으라고 했으므로 A 뒤에 두 문자열의 공통 부분 수열을 제외한 새로운 B 문자열을 연결한 형태가 될 것 이다.
  ex) "beakjoon" + "hongjun" -> "beakjoon" + "hongu" = "beakjoonhongu"
• LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 DP를 사용하여 해결할 수 있다. 자세한 설명은 아래 링크를 참조하자.
  [이론] 최장 공통 부분 수열 (LCS, Longest Common Subsequence)

---

 ⌨️ C++ 코드

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

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

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

    for (int i = 1; i <= l1; i++) {
        for (int j = 1; j <= l2; j++) {
            if (str1[i - 1] == str2[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 << l1 + l2 - dp[l1][l2];
}