SW Expert Academy 의 1264번 - 이미지 유사도 검사 문제입니다.
- 난이도 : 5
문제 조건
문제 설명에서 4가지 상태라던지, 기타 다른 용어를 첨가하였지만
사실 이 문제는 LCS의 길이를 구하는 문제와 완전히 동일합니다.
LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘에 대한 포스팅
Input
한 개의 테스트 케이스 당
이미지 스캔 코드열의 크기 N(N<=500)
그 다음줄에는 첫 번째 코드열 X
그 다음줄에는 두 번째 코드열 Y
가 차례로 주어진다.
Output
X와 Y의 최장 공통 부분 문자열의 길이를 출력한다.
소스코드
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int arr[501][501]; // 0으로 초기화 됨
int main() {
int T, N;
int str1Len, str2Len;
char str1[501];
char str2[501];
double result;
scanf("%d", &T);
for (int t = 1; t <= T; t++) {
scanf("%d", &N);
scanf("%s", &str1);
scanf("%s", &str2);
str1Len = strlen(str1);
str2Len = strlen(str2);
//첫행과 첫열은 0인 상태.
for (int j = 0; j < str2Len; j++) {
for (int i = 0; i < str1Len; i++) {
// 문자열이 다를 경우
if (str1[i] != str2[j]) {
// 현재 위치(arr[j+1][i+1])에서 위쪽값이 왼쪽값보다 크면
if (arr[j][i+1] >= arr[j+1][i])
arr[j + 1][i + 1] = arr[j][i + 1];
// 현재 위치(arr[j+1][i+1])에서 왼쪽값이 위쪽값보다 크면
else if (arr[j][i + 1] <= arr[j + 1][i])
arr[j + 1][i + 1] = arr[j + 1][i];
}
// 문자열이 같을 경우, 현재 위치의 대각선 값 + 1
else {
arr[j + 1][i + 1] = arr[j][i] + 1;
}
}
}
result = double(arr[str2Len][str1Len]);
printf("#%d %.2f\n", t, result / N * 100);
// arr 초기화
for (int i = 0; i < N + 1; i++) {
for (int j = 0; j < N + 1; j++){
arr[i][j] = 0;
}
}
}
}