[1264번] 이미지 유사도 검사

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18Q_MqIvUCFAZN

알고리즘 분석 :

문제 해결에 필요한 사항

1. LCS 알고리즘

lcs 알고리즘을 이용하면 쉽게 해결 할 수 있다.

lcs :: https://www.crocus.co.kr/787

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <iostream> #define max(a,b)(a > b? a : b) int lcs[505][505]; char str1[505]; char str2[505];   int main() {     int tCase;     scanf("%d", &tCase);       for (int tc = 1; tc <= tCase; tc++) {         int n;         scanf("%d", &n);           str1[0] = str2[0] = '0';         scanf("%s", str1 + 1);         scanf("%s", str2 + 1);           for (int i = 0; i < n + 1; i++) {             for (int j = 0; j < n + 1; j++) {                 if (!i || !j) {                     lcs[i][j] = 0;                     continue;                 }                 if (str1[i] == str2[j])                     lcs[i][j] = lcs[i - 1][j - 1] + 1;                 else                     lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);             }         }           printf("#%d %.2lf\n", tc, 1.0 * lcs[n][n] / n * 100);     }     return 0; }   Colored by Color Scripter

cs