Beakjoon 9251 LCS

24 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/9251

나의 풀이

두 문자열 str1과 str2의 LCS를 구하고자 할 때 DP를 다음과 같이 정의하였다.
DP[i][j] = str1의 i번째 문자까지, str2의 j번째 문자까지의 LCS 길이
str1 = “BCD”, str2 = “BDA”일 때를 생각해보자.


먼저 str1의 1번째 까지의 문자열과, str2의 1번째 까지의 문자열을 확인해 보면 둘 다 ‘B’인 것을 확인할 수 있다.
이 상황에서 “B”와 “B”의 LCS를 구하면 값은 1이 나온다.

같은 방식으로 str1의 1번째 까지의 문자열과, str2의 2, 3번째 까지의 문자열을 확인해 보면 str1[i]값과 str2[j]값이 다르기 때문에 LCS의 길이의 영향을 주지 못하고 기존에 만들어진 LCS “B”에 의해 길이가 결정이 된다.

다음으로 str1의 2번째까지의 문자열과, str2의 1번째 까지의 문자열을 확인해보면 각각 “B”와 “BD”로 “BD”의 “D”는 LCS의 영향을 주지 못하고 이전에 만들어진 LCS “B”에 의해 길이가 결정된다.

i=3, j=2일 때는 “BCD”, “BD”를 비교하게 되고, 마지막 값이 ‘D’로 같기 때문에 “BCD”와 “BD”에서의 LCS는 결국 “BC”와 “B”사이에서 구한 LCS 맨 뒤에 “D”를 추가해 주는것과 같다.

최종적으로 다음과 같은 결과를 얻을 수 있다.

str1[i]까지의 문자열과 str2[j]까지의 문자열의 LCS를 구하는 과정을 두 가지로 분류할 수 있다.
만약 str1[i] == str2[j]를 만족한다면 str1[i-1]까지의 문자열과 str2[j-1]까지의 문자열로 만들 수 있는 LCS에 str1[i]를 추가하는 것이 (i, j)에서의 LCS이다. 떄문에 이전에 만들었던 LCS 길이에 +1을 해주면 다음과 같은 결과를 얻을 수 있다.
DP[i][j] = DP[i-1][j-1] + 1
만약 str1[i]와 str2[j]의 값이 서로 다르다면 (i, j) 직전 즉 (i-1, j) or (i, j-1)에서 만들 수 있는 LCS 중 더 큰 값을 따르게된다.
DP[i][j] = max(DP[i-1][j], DP[i][j-1])

풀이 코드 : 9251 LCS

#include <vector>
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int DP[1001][1001];

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

    string str1, str2;

    cin>>str1;
    cin>>str2;

    for(int i=1;i<=str1.size();i++){
        for(int j=1;j<=str2.size();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<<DP[str1.size()][str2.size()];

}

채점결과