[백준 9251][파이썬] LCS (최장 공통 부분 수열)

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

9251번: LCS

dp[x][y]를 다음과 같이 정의한다.

 

dp[x][y]는 첫 번째로 입력받은 문자열을 s1이라 하고 두 번째로 입력받은 문자열을 s2라고 한다면

 

s1에서 x번째 문자까지와 s2에서 y번째 문자까지를 비교했을 때 최장 공통 부분 수열의 길이이다.

 

예를 들어 dp[2][4]라고 한다면 "AC"와 "CAPC"의 최장 공통 부분 수열의 길이인 "AC"즉, 2이다.

 

이를 활용하여 dp를 적용하면 된다.

 

dp[x][y]를 구할 때는 우선 s1의 x번째 문자를 s2의 모든 문자와 비교한다.

 

만약 같은 문자가 나온다면 dp[x][y]는 dp[x-1][y-1] + 1이 된다.

 

나오지 않는다면 dp[x-1][y]와 dp[x][y-1]중 큰 값이 dp[x][y]의 값이 된다.

 

여기서 중요한 점은 dp[x][y]에서 x나 y, 둘 중 하나라도 0이 존재하면 그 값은 0으로 만들고 1부터 시작해야한다.

 

0부터 시작하면 dp[x-1][y-1] 값을 구할 때 인덱스가 음수가 되어 에러가 발생하기 때문이다.

 

<전체 코드>

import sys
input=sys.stdin.readline

#인덱스 맞추기 위해 앞에 의미없는 문자 추가. 
s1 = [0]+list(input().rstrip())
s2 = [0]+list(input().rstrip())

#dp[x][y] 
#첫 번째 문자열 x번째까지와 두 번째 문자열 y번째까지 비교했을 때 LCS 길이

dp=[[0]*len(s2) for _ in range(len(s1))]
for i in range(1, len(s1)):
    for j in range(1, len(s2)):
        if s1[i]==s2[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i][j-1], dp[i-1][j])
print(dp[len(s1)-1][len(s2)-1])