[BOJ/백준] LCS 2 9252 gold4 / DP / python

문제

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

출력형태를 보니 최장 공통 부분수열의 길이만 알 수 있던 일반적인 LCS 알고리즘 풀이에 LCS 문장을 출력하는 부분이 추가가 되었다.

첫번째 풀이

import sys

str1 = str(sys.stdin.readline().strip())
str2 = str(sys.stdin.readline().strip())
dp = [[[0, ''] for _ in range(len(str1) + 1)] for _ in range(len(str2) + 1)]

for i in range(0, len(str2)):
    for j in range(0, len(str1)):
        if str1[j] == str2[i]:
            dp[i + 1][j + 1][0] = dp[i][j][0] + 1
            dp[i + 1][j + 1][1] = dp[i][j][1] + str1[j]
        else:
            dp[i + 1][j + 1][0] = max(dp[i + 1][j][0], dp[i][j + 1][0])
            if len(dp[i][j + 1][1]) > len(dp[i + 1][j][1]):
                dp[i + 1][j + 1][1] = dp[i][j + 1][1]
            else:
                dp[i + 1][j + 1][1] = dp[i + 1][j][1]

if dp[len(str2)][len(str1)][0] > 0:
    print(dp[len(str2)][len(str1)][0])
    print(dp[len(str2)][len(str1)][1])
else:
    print(0)

LCS 알고리즘 dp 풀이에는 LCS의 길이만 저장이 되는데, LCS를 저장하기 위한 리스트를 [0,''] <- 이런식으로 해당 LCS 문자열까지 저장할 수 있는 형태로 만들어서 풀었다.
풀리긴했지만 다른 사람들 풀이를 찾아보니... 나처럼 푼사람은 못본거같다 🥲

개선한 풀이

import sys

str1=str(sys.stdin.readline().strip())
str2=str(sys.stdin.readline().strip())
dp=[[0]*(len(str1)+1) for _ in range(len(str2)+1)]

for i in range(len(str1)):
    for j in range(len(str2)):
        if str2[j]==str1[i]:
            dp[j+1][i+1]=dp[j][i]+1
        else:
            dp[j+1][i+1]=max(dp[j+1][i],dp[j][i+1])

# lcs찾기
r=len(str2)
c=len(str1)
print(dp[r][c])
ans=''
while r>0 and c>0:
    if dp[r][c-1]==dp[r][c]:
        c-=1
    elif dp[r-1][c]==dp[r][c]:
        r-=1
    else:
        ans+=str2[r-1]
        r-=1
        c-=1

print(ans[::-1])

LCS 알고리즘으로 완성된 DP 테이블의 r,c에서부터 역추적하며 어떤 문자열을 ans에 추가할건지 탐색하면 된다.

• 테이블 현재 r,c 기준으로 r,c-1 칸의 값과 같다면 r,c-1로 이동시킨다.
• 테이블 현재 r,c 기준으로 r-1,c 칸의 값과 같다면 r-1,c칸으로 이동시킨다.
• 둘 다 아니라면 (r,c-1 과 r-1,c 칸 모두 현재 r,c와 다르다면) r-1,c-1칸으로 이동시킨다. 그리고 이 경우에 ans에 해당 문자를 넣는다.
• r,c의 값이 0이하가 되면 반복을 종료한다.

개선한 방법으로 다시 푸니까 훨씬 빠른 속도로 채점이 끝났다 ~!