[백준 알고리즘] 9252번 LCS 2 최장 공통 부분 수열. 파이썬(python)

 

역추적을 할 때 현재-1이 왼쪽, 위랑 같을 때 공통된 문자로 취급

처음에 왼쪽==위 일 때 공통되었다고 생각했는데

dp가 

1 1

1 1

과 같이 값이 세 개가 다같은 경우가 있어서 안됨

 

import sys
input=sys.stdin.readline

s1=input().rstrip()
s2=input().rstrip()
dp=[[0]*(len(s2)+1) for _ in range(len(s1)+1)]
answer=''
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])

# dp배열을 역추적하면서 값을 찾는다.
i=len(s1)
j=len(s2)
while dp[i][j]!=0:
    if dp[i][j]-1==dp[i-1][j] and dp[i][j]-1==dp[i][j-1]:
        answer=s1[i-1]+answer
        i-=1
        j-=1
    else:
        if dp[i-1][j]>dp[i][j-1]: # 위>왼쪽
            i-=1
        else: # 위<왼쪽
            j-=1

print(dp[-1][-1])
print(answer)