[백준 9251] LCS [C]

백준 - 9251

---

풀이

첫째 줄에 입력받은 문자열의 각 문자와 둘째 줄에 입력받은 문자열간의 LCS를 구하는 방식으로 풀이했다.

(j, i)번째에 각 문자열의 문자가 동일하다면, (j-1, i-1)번째의 LCS보다 1만큼 길다.

만약 문자가 같지않다면, 이전 LCS의 값 중 큰 값과 일치한다.

---

소스코드

#include <stdio.h>
#define max(a, b) a > b ? a : b
int dp[1001][1001];
int main(){
    char str[2][1001];
    scanf("%s %s", &str[0], &str[1]);
    int i, j;
    for (i = 0; str[0][i]; i++)
        for (j = 0; str[1][j]; j++)
            if (str[0][i] == str[1][j]) dp[j+1][i+1] = dp[j][i] +1;
            else dp[j+1][i+1] = max(dp[j][i+1], dp[j+1][i]);
			
    printf("%d", dp[j][i]);
}

---

출처

9251번: LCS