[9251] LCS

풀기전에 '뇌를 자극하는 알고리즘'이라는 책에서 예제를 본적이 있어 비교적 쉽게 풀 수 있었다.

#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
​
int main(){
    char N1[1001];
    char N2[1001];
    int d[1002][1002]={};
    scanf("%s",N1);
    scanf("%s",N2);
​
    int len1 = strlen(N1);
    int len2 = strlen(N2);
    for(int i = 0;i<=len1;i++){
        d[i][0] = 0;
    }
    for(int i = 0;i<=len2;i++){
        d[0][i] = 0;
    }
​
    for(int i = 1;i<=len1;i++){
        for(int j = 1;j<=len2;j++){
​
            if(N1[i-1] == N2[j-1]){
                d[i][j] = d[i-1][j-1]+1;
            }else{
                d[i][j] = max(d[i-1][j],d[i][j-1]);
            }
        }
    }
​
    printf("%d\n",d[len1][len2]);
​
}

점화식은 다음과 같다.

1. 두 문장의 길이가 모두 0일때 --- d[i][0], d[0][i] = 0

2. 두 문장의 맨 끝 글자가 같을때 --- d[i][j] = d[i-1][j-1]+1

3. 두문장의 길이가 0이 아니고 끝글자가 다를때 --- d[i][j] = max(d[i-1][j], d[i][j-1])

두문장의 맨 끝글자가 같으면 두 문장의 전 글자까지 계산한 d[i-1][j-1]에다 1을 더하면 d[i][j]가된다.

두문장의 끝글자가 다르면 문자1의 맨 끝글자와 문장2의 문장 끝에서 두번째 글자가 같을 수 있고 그 반대의 순서도 가능하므로

둘중 큰값을 d[i][j]에 넣는다.