[백준] 9251 LCS(C++)

 

문제 URL:

https://www.acmicpc.net/problem/9251

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력하는 프로그램을 작성하자.

*최장 공통 부분 문자열은 연속되어야 하지만 최장 공통 부분 수열은 연속되지 않아도 됨

 

다음 문제는 다이나믹 프로그래밍을 이용하여 푸는 문제로 예시를 통해서 문제를 이해해 보자.

 

i: 문자열 A의 문자 중 하나의 위치

j: 문자열 B의 문자 중 하나의 위치

DP[i][j]: 처음~i와 처음~j를 비교했을 때까지의 공통 부분 수열의 최대 길이

 

먼저, 비교하는 두 문자가 같을 때이다.

문자열 "ABDEG"와 "ABECG"가 존재할 때 마지막 G에서 값은 "ABDE"와 "ABEC" 까지의 최장 공통 부분수열 + 1이 된다. 

이를 DP를 이용한 식으로 나타내면 다음과 같다.

DP[i][j] = DP[i-1][j-1] + 1;

 

반대로 4번째 자리의 E와 C 같이  비교하는 두 문자가 다를 때에는

이전 "ABD", "ABE"까지의 최장 공통 부분 수열에 E를 포함한 경우와 C를 포함한 경우를 각각 두고 둘 중 더 큰 값을 취하면 된다.

식으로 표현하면 다음과 같다. 

DP[i][j] = max(DP[i-1][j], DP[i][j-1]);  // max(): algorithm 헤더의 함수

 

위 과정을 포함한 문자 비교를 두 문자열이 끝날 때까지 수행하면 마지막 DP에 두 문자열의 최장 공통 부분 수열의 길이가 저장된다.

---

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string A, B;
int DP[1001][1001];  // 처음~i와 처음~j를 비교했을 때까지의 공통 부분 수열의 최대 길이

int main(){
    cin >> A >> B;
    
    int a_size = A.size();
    int b_size = B.size();
    
    for(int i=1; i<=a_size; i++){
        for(int j=1; j<=b_size; 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]);
        }
    }
    
    cout << DP[a_size][b_size] << '\n';
    return 0;
}

출처: https://yabmoons.tistory.com/113