백준 9251 LCS

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

9251번: LCS

 

 

 

EXPLANATION

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)

 

이 문제를 푸는 코드는 직관적으로 이해하기 쉽다.

 

첫번째 문자열에서 i번째 문자를 a[i]라 하고

두번째 문자열에서 j번째 문자를 b[j]라 하자.

 

첫번째 문자열에서 i번째까지와,

두번째 문자열에서 j번째까지를 

비교했을 때 구해지는 LCS의 길이를 dp[i][j]라 하자.

 

a[i]와 b[j]가 같을 때,

dp[i][j] = dp[ i-1 ][ j-1 ] + 1이다.

 

a[i]와 b[j]가 다를 때,

dp[i][j] = max( dp[i][j-1], dp[i-1][j] )이다.

 

예제와 함께 살펴 보자

A C A Y K P
C A P C A K

 

ex)

dp[4][5]를 구해보자.

a[4] == b[5]

=> dp[4][5] = dp[3][4] + 1

= 3 + 1 = 4

 

A C A Y  K P
C A P C A  K

 

 

dp[5][5]를 구해보자.

a[5] != b[5]

=> dp[5]dp[5] = max(dp[5][4], dp[4][5]) = max(3, 4)

= 4

 

A C A Y K P
C A P C A  K

 

A C A Y K P 
C A P C A K 

 

 

i나 j 둘 중에 하나가 0이면 위의 규칙을 따를 때 음의 index가 발생한다.

따라서 여기서 base를 나타내야 한다.

dp[0][j] = dp[0][j] = 0 

한 문자열에서 0번째까지와

나머지 다른 문자열에서 i 또는 j번째까지를 비교했을 때

구해지는 LCS의 길이는 당연히 0이다. 

한 문자열에서 비교 가능한 문자가 애초에 존재하지 않으므로.

 

 

 

점화식

dp[i][0] = dp[0][j] = 0

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]);

 

 

 

CODE

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

const int MAX = 1001;    //for[0,string.length()]
int dp[MAX][MAX];    //0으로 초기화 됨. 자동으로 base 설정: dp[i][0] = dp[j][0] = 0, string의 index는 0부터 시작.

int main(){
    string a, b;
    cin >> a >> b;

    int a_size = a.length();
    int b_size = b.length();
                                         
    for (int i = 1; i <= a_size; i++)    //base: dp[i][0]= dp[0][j] = 0. 제외하고 i=1, j=1부터 
        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;
}