[코딩 테스트 연습(파이썬/Python)] 백준 9251번 _ LCS

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

9251번: LCS

[문제]

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

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

 

[입력]

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

[출력]

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

[아이디어]

1) 두 문자열(s1,s2)의 맨 뒤 문자가 같을 때와 다를 때로 구분할 수 있다.

-> 같을 때: LCS(s1[:-1], s2[:-1])+1

-> 다를 때: LCS(s1, s2[:-1]) or LCS(s1[:-1], s2) 중 큰 값. (둘 중 하나의 마지막 문자는 LCS에 포함될 수 있다.)

 

s1=input()
s2=input()
n=len(s1); m=len(s2)
dp=[[0]*(m+1) for _ in range(n+1)]
for i,x in enumerate(s1):
    for j, y in enumerate(s2):
        if x==y:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
print(dp[-1][-1])

아래처럼 뒤에서부터 역추적하는 코드도 있었다.

a=input()
b=input()[::-1]
d=[0]*len(b)
for i in a:
    n=0
    for j in b:
        if i==j:
            d[n]=max(d[n+1:],default=0)+1
        n+=1
    print(i, d)

뒤에서부터 반복문으로 돌리면서, 같아진 위치 이전까지의 공통 부분 길이에 +1을 해주는 방식으로 업데이트 해 나가는 것 같다. 결국 뒤에서부터 확인해야함은 동일하다. 해당 부분 수열이 무엇인지 파악하는 문제도 있으니, 그걸 풀 때 조금 더 자세히 살펴봐야겠다.