백준(C) 9251번 [LCS]

LCS 9251번

 

현대 오토에버 대비 다이나믹 프로그래밍 문제중 하나인 LCS(최장 공통 부분 수열)문제이다.

말그대로 두 수열이 주어졌을때 두 부분 수열이 되는 수열중 가장 긴 것을 찾는 것이다.

0부터 n까지 공통된 문자만 찾아서 비교하면된다. 문자열의 문자는 정해지지 않으므로

찾으려는 결과 값은 dp[i][j] = 문자열 a의 i글자와 문자열 b의 j글자 간의 공통 수열 길이 
이렇게 나타낼수있다. 그렇다면 초기값은 dp[0][j] = 0, dp[i][0] = 0이다.

그리고 앞에 배낭문제처럼 이 문제도 만약 공통된 수를 찾으면 value를 증가 시키면 된다. 이때 value 값은 +1 이다.

그렇다면 점화식을 구할수있다. dp[i][j] = dp[i-1][j-1] +1 이다.

처음엔 dp[i][j] +1 를 적용 시킬까 생각을 했는데 DP 의 본질은 문제를 하위 문제로 나누는 것이므로 

dp[i-1][j-1] +1로 다시 정정했다.

 

이 문제도 생각하면 생각할수록 어렵지만 DP적 사고를 가지면 매우 쉽게 풀수있는 문제중 하나 이다.

 

코드는 다음과 같다 .

#include <stdio.h>
#include <string.h>

int dp[1001][1001];

int main(void) {
    char a[1001], b[1001];

    scanf("%s %s", a, b);

    int a_len = strlen(a);
    int b_len = strlen(b);

    for(int i = 1; i <= a_len; i++){
        for(int j = 1; j <= b_len; j++){
            if(a[i-1] == b[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                if(dp[i-1][j] > dp[i][j-1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
    }

    printf("%d\n", dp[a_len][b_len]);

    return 0;
}