백준 9251번: LCS
Longest Common Subsequence
아이디어
DP 테이블에 해당 문자열로 만들 수 있는 Longest Common Subsequence의 길이를 저장한다.
2차원 배열의 인덱스와 두 문자열의 인덱스를 매칭시킨다. 예를 들어 주어진 문자열이 ACAYKP, CAPCAK라 하자. 이 때 dp[2][5]에는 AC와 CAPCA의 Longest Common Subsequence 길이를 저장한다. 그 길이는 2가 될 것이다. dp[2][6]에는 ACA와 CAPCA의 LCS 길이를 저장한다. 그 길이는 3이 될 것이다.
코드
import sys
input = sys.stdin.readline
str1 = input().rstrip()
str2 = input().rstrip()
dp = [[0] * 1001 for _ in range(1001)]
for i in range(1, len(str1)+1):
for j in range(1, len(str2)+1):
if str1[i-1] == str2[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[len(str1)][len(str2)])
여담
LCS와 관련된 문제가 굉장히 많다. 다 풀어보면 큰 도움이 될 것이다.
백준 9252번: LCS2
백준 1958번: LCS3
백준 5582번: 공통 부분 문자열
Author And Source
이 문제에 관하여(백준 9251번: LCS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-9251번-LCS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)