[C++] 백준 - 11056번 문제

11056번: 두 부분 문자열 (acmicpc.net)

11056번: 두 부분 문자열

 

11056번 : 두 부분 문자열

---

두 문자열 A와 B가 주어진다. 이때, A와 B를 부분 문자열로 가지는 문자열 S를 구하는 프로그램을 작성하시오. 가능한 S가 여러 가지인 경우 길이가 가장 짧은 것을 출력한다.

예를 들어, A = "baekjoon", B = "hongjun"인 경우 가능한 S중 길이가 가장 짧은 것 중 하나는 "baekhongjouon"이다.

 

입력

---

첫째 줄에 문자열 A, 둘째 줄에 문자열 B가 주어진다. 두 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

 

 

출력

---

첫째 줄에 A와 B를 부분 문자열로 가지는 가장 짧은 S의 길이를 출력한다.

 

 

 

---

 

생각해 볼 점

---

DP 문제입니다.

 

정확히는 LCS 유형의 문제이니 LCS 문제 풀이와 동일하게 풀면 되겠습니다.

 

 

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

코드

---

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

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

    string A, B;

    cin >> A >> B;

    vector<vector<int>> dp(A.length() + 1, vector<int>(B.length() + 1, 0));

    //LCS
    for(int i = 1; i <= A.length(); i++)
    {
        for(int j = 1; j <= B.length(); j++)
        {
            if(A[i - 1] == B[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    printf("%d", A.length() + B.length() - dp[A.length()][B.length()]);
    return 0;
}

 

그 외

---