Baekjoon 9251 (LCS)

Baekjoon 9251, 백준 9251 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제 보기

#include <stdio.h>
#include <string.h>
#define MAX(x,y) ( (x)>(y) ? (x) : (y) )

char a[1001], b[1001];  // 입력받는 두 문자
int dp[1001][1001] = {0,}; // 2*2 배열을 만든다.
// dp[i][j]는 a의 i번째 글자까지와 b의 j번째 글자까지의 LCS를 의미함.

int main(){
    scanf("%s",a);
    scanf("%s",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 dp[i][j] = MAX(dp[i][j-1], dp[i-1][j]);
        }
    }

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

LCS algorithm을 이용하면 쉽게 풀리지만, 모른다면 꽤 복잡해 질 것 같은 문제.