이미지 유사도 검사

1. 이미지 유사도 검사

2. DP로 공통 부분 문자열을 찾을 수 있구나

3. 이렇게 풀어 나가는 것은 

4. 디피 관련 문제를 찾아봐야 하고, 어떤 것은 어떻게 풀리는지 보기

5. 풀 수 있는 유형이 분명히 정해져 있음

#include <stdio.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))

#define MAX 12
char str1[MAX];
char str2[MAX];
int dp[MAX][MAX];

int main()
{
    freopen("input.txt", "r", stdin);
    int T, test_case;
    int N;
    int i, j;

    setbuf(stdout, NULL);
    scanf("%d", &test_case);
    for (T = 1; T <= test_case; ++T)
    {
        scanf("%d", &N);
        scanf("%s", str1 + 1);
        scanf("%s", str2 + 1);
        for (i = 1; i <= N; ++i)
        {
            for (j = 1; j <= N; ++j)
            {
                if (str1[i] == str2[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1; // str1의 인덱스와 str2의 인덱스 해당하는 부분에 저장
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        printf("#%d %.2lf\n", T, (double)dp[N][N] / N * 100);
    }

    return 0;
}