[백준 | DP] 9251번 LCS - python

문제 링크

https://www.acmicpc.net/problem/9251

9251번: LCS

---

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

---

해결

str1: 처음 입력받은 string ACAYKP

str2: 두번째로 입력받은 string CAPCAK

dp[i][j]: str1 i번째까지와 str2 j번째까지의 LCS 길이

 

문제에서 제시해준 예시로 풀어보자.

 

str1: A

str2: C

두 문자열로 만들 수 있는 LCS의 길이는 0이다. (dp[1][1] = 0)

 

str1: A

str2: CA

두 문자열로 만들 수 있는 LCS의 길이는 1이다. (dp[1][2] = 1)

 

str1: A

str2: CAP

두 문자열로 만들 수 있는 LCS의 길이는 1이다. (dp[1][3] = 1)

 

str1: A

str2: CAPC

두 문자열로 만들 수 있는 LCS의 길이는 1이다. (dp[1][4] = 1)

 

위와 같이 str2의 끝까지 계산해주었다면, str1을 하나씩 늘려주면 된다.

 

str1: AC

str2: C

두 문자열로 만들 수 있는 LCS의 길이는 1이다. (dp[2][1] = 1)

 

str1: AC

str2: CA

두 문자열로 만들 수 있는 LCS의 길이는 1이다. (dp[2][2] = 1)

.

.

.

 

두가지 경우로 나눌 수 있다.

1) 추가된 알파벳이 str1[i] == str2[j] 인 경우

: LCS 최대 길이를 +1 만큼 늘려 줄 것이다.

: dp[i][j] = dp[i-1][j-1] + 1

 

2) 추가된 알파벳이 str1[i] != str2[j] 인 경우

: 추가된 알파벳은 길이 증가에 영향을 주지 않기 때문에, 추가되기 전의 알파벳들로 LCS 길이를 비교한다.

: dp[i][j] = max(dp[i][j-1], dp[i-1][j])

 

풀 때 사용한 노트

 

---

코드

str1 = ' '+input()
str2 = ' '+input()
len_str1 =len(str1)
len_str2 =len(str2)
dp = [[0]*len_str2 for _ in range(len_str1)]

for i in range(1,len_str1):
    for j in range(1,len_str2):
        if str1[i] == str2[j]:
            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])