(9251)(DP) 백준 LCS

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

풀이

---

1.    arr[i]와 arr[j]가 일치할 경우

dp[i][j] = dp[i - 1][j - 1] + 1;

2. 일치하지 않을경우 

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

그림 출처    :    https://m.blog.naver.com/PostView.nhn blogId=tjdwns0920&logNo=221129635977&targetKeyword=&targetRecommendationCode=1&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

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