[백준알고리즘] 9252번: LCS 2 -Python

[백준알고리즘] 9252번: LCS 2 -Python

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

9252번: LCS 2

이전에 LCS 문제를 푼 적이 있다. 아래는 그때 풀었던 코드이다.

https://suri78.tistory.com/11

 

오랜만에 LCS 문제를 풀려니까 머리가 아팠었다. 결국 방식은 동일하게 됐었다.

다만 문자열도 출력해주어야 하기 때문에 memoization 할 때 문자열을 직접 넣어주었다.

 

처음에는 s1[i] == s2[j] 일 때 dp[i][j] = dp[i-1][j] + s1[i]와 같은 식으로 늘려주었는데 이렇게 dp[i-1][j-1]에 더해주는 것이 아닌 방식은 중복해서 문자를 더하는 문제가 발생할 수 있다.

 

s1 = input().rstrip()
s2 = input().rstrip()
len_s1 = len(s1)
len_s2 = len(s2)
dp = [['']*len_s2 for _ in range(len_s1)]

for i in range(len_s1):
    dp[i][0] = s2[0] if s2[0] == s1[i] else dp[i-1][0]
for j in range(len_s2):
    dp[0][j] = s1[0] if s1[0] == s2[j] else dp[0][j-1]

for i in range(1, len_s1):
    for j in range(1, len_s2):
        dp[i][j] = dp[i][j-1] if len(dp[i][j-1]) >= len(dp[i-1][j]) else dp[i-1][j]
        if s1[i] == s2[j] and len(dp[i-1][j-1]) >= len(dp[i][j]):
            dp[i][j] = dp[i-1][j-1] + s1[i]

ans = dp[-1][-1]
print(len(ans))
if len(ans) > 0:
    print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다