[백준/C++][LCS(9251번)]-LCS 알고리즘

문제

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

9251번: LCS

X문자열과 Y문자열이 있다고 하자.

X 문자열은 X(1)~X(i)까지 있다고 하고 Y문자열은 Y(1)~Y(j)까지 있다고 하자.

X(i)와 Y(j)가 같은 경우와 다른 경우가 있을 수 있다.

 

-만약 X(i)와 Y(j)가 같은 경우라면 X(1)~X(i-1),  Y(1)~Y(j-1)의 LCS길이를 구하면 된다. 그리고 마지막 문자가 추가됨으로써 +1을 해주면 LCS(i, j)일 때의 값이 나오게 된다.

LCS(i, j)  = LCS(i-1, j-1)+1;

-만약 X(i)와 Y(j)가 다른 경우라면 X(i)또는 Y(j) 하나만 고를 수 있다.

X(i)을 선택한 경우

X(1)~X(i), Y(1)~Y(j-1)의 LCS길이

Y(i)을 선택한 경우

Y(1)~Y(j), X(1)~X(i-1)의 LCS길이

이렇게 2개의 길이를 구할 수 있다

그러면 LCS(i, j) = max(LCS(i, j-1),LCS(i-1, j)) 라는 식을 구할 수 있다.

 

정리를 해보자면 

LCS(i, j)  = LCS(i-1,j-1)+1;  if(X(i) == Y(j))

LCS(i,j) = max(LCS(i, j-1), LCS(i-1, j)) if(X(i)!= Y(j))

라는 식을 얻을 수 있다.

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
int LCS[1002][1002];
char st1[1001],st2[1001];
int main(void){
    memset(LCS,0,sizeof(LCS));
    cin >> st1 >> st2;
    int st1_size = strlen(st1);
    int st2_size = strlen(st2);
    for(int i = 1;i<=st2_size;i++){
        for(int j = 1;j<=st1_size;j++){
            if(st2[i-1] == st1[j-1]){
                LCS[i][j] = LCS[i-1][j-1]+1;
            }
            else{
                LCS[i][j] = max(LCS[i-1][j],LCS[i][j-1]);
            }
        }
    }
    cout << LCS[st2_size][st1_size];
}