백준 9251번, LCS(C, C++)

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

9251번: LCS

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

#include<iostream>
#include<algorithm>

using namespace std;

int LCS[1001][1001];

int main(){
    string str1;
    string str2;
    cin>>str1;
    cin>>str2;
    int maxi = 0;

    for(int i = 1; i <= str1.length(); i++){
        for(int j = 1; j <= str2.length(); j++){
            if(str1[i-1] == str2[j-1]){
                LCS[i][j] = LCS[i-1][j-1] + 1;
            }else{
                LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
            }
        }
    }
    for(int i = 1; i <= str1.length(); i++){
        for(int j =1; j <= str2.length(); j++){
            if(maxi < LCS[i][j]){
                maxi = LCS[i][j];
            }
        }
    }
    cout<<maxi;
}

직관적으로 생각했을 때,  CA와 ACA를 비교했을 때 LCS는 2입니다.

가로축의 ACA에서 마지막 A가 빠진 상태의 AC와 세로축의 C의 LCS는 1입니다.

여기서 가로축의 ACA의 맨 뒷자리의 A가 세로축의 CA의 A와 같은데,  AC가 가지고 있는 LCS길이 값을 +1 해준다는 것을 알 수 있습니다.

즉 맨 뒷자리의 문자가 같은 경우, 각 둘의 뒷자리를 포함하기전(AC, C)의 문자 LCS[i-1[j-1]에 +1를 해주면 된다는 뜻 입니다.

 

 

이제 마지막 문자가 서로 다른 경우를 찾아봅시다.

C와 ACA를 살펴봅시다.

마지막 단어가 C와 A로 서로 다릅니다.

C와 AC의 LCS길이에 영향을 받는 것을 알 수 있습니다.

위 그림대로 CAP와 ACA의 LCS를 구하면,

CA와 ACA의 LCS길이에 영향을 받은 걸 볼 수 있습니다.

 

※ 즉, 영향을 받는 경우는 2가지인데, 이 중에서 큰 값이 해당 LCS길이입니다.

위의 문장을 코드로 표현하면 max(LCS[i-1][j], LCS[i][j-1])가 될 수 있겠습니다.

 

if문을 사용해 맨 마지막의 문자가 같은 경우와 틀린 경우로 나눠 반복문을 사용하게 되면

LCS 2차원 배열에 가장 큰 값이 저장됩니다.