[SWEA] 1264. [S/W 문제해결 응용] 8일차 - 이미지 유사도 검사(python)

문제 url : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18Q_MqIvUCFAZN&categoryId=AV18Q_MqIvUCFAZN&categoryType=CODE&problemTitle=%EC%9D%91%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

문제접근법 : 

LCS를 이용한 문제입니다.

최장공통부분문자의 길이가 즉 가장 유사도가 높고

백분율 이용해서 답을 내주시면 됩니다.

 

소스코드:

from collections import defaultdict
#import sys
#sys.stdin = open("input.txt","r")
Test = int(input())
for test in range(1,Test+1):
    n = int(input())
    s1 = input()
    s2 = input()
    dp = [[0]*(n+1) for i in range(n+1)]
    res = 0
    for i in range(n):
        for j in range(n):
            if s1[i]==s2[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
            res = max(res,dp[i+1][j+1])
    print('#%d %.2f'%(test,res*100/n))

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.