[백준-9251] LCS
풀이
사진 출처: https://myjamong.tistory.com/317ACAYKP 와 CAPCAK 를 예시로 앞의 문장의 sub sequence를 a, 뒤에 문장의 sub sequence를 b라 하면
a:A
b:CA
두 문자열로 만들 수 있는 LCS의 길이: 1
a:A
b:CA
두 문자열로 만들 수 있는 LCS의 길이:1
...위와 같이 b를 하나씩 늘려가면서 LCS의 길이를 구하고 b를 다 늘렸으면 a를 늘려서 다시 위와같이 LCS의 길이를 구한다.
a:AC
b:C
두 문자열로 만들 수 있는 LCS의 길이:1
a:AC
b:CA
두 문자열로 만들 수 있는 LCS의 길이:1
이때 만약 a와b에 추가된 문자가 같다면 a와b에 둘다에 문자가 추가되기전 LCS길이에+1을 해준값이 추가된 문자가 같을때의 LCS길이가 된다.
dp[i][j]=dp[i-1][j-1]+1
a와b에 추가된 문자가 다르다면 기존에 주어진 문자열로 만들 수 있는 최대 길이가 LCS길이가 된다.
dp[i][j]=max(dp[i-1][j],dp[i][j-])
코드
import sys
input = sys.stdin.readline
s1=input().strip()
s2=input().strip()
dp=[[0]*(len(s2)+1) for _ in range(len(s1)+1)]
for i in range(1,len(s1)+1):
for j in range(1,len(s2)+1):
if s1[i-1]==s2[j-1]:
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])
수행시간 : 712ms
Author And Source
이 문제에 관하여([백준-9251] LCS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sue06004/백준-9251-LCS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)