090 LCS 2

첫번째 코드

 

우울해하지 말고!!

점화식을 만드는 방법이 이렇게 있구나~ 하면서 배워가기!

 

코드는 책을 참고했다!

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

a = list(input())
a.pop()
b = list(input())
b.pop()

dp = [[0 for _ in range(len(b) + 1)] for _ in range(len(a) + 1)]
path = []

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[len(a)][len(b)])

def getText(r, c):
    if r == 0 or c == 0:
        return
    if a[r-1] == b[c-1]:
        path.append(a[r-1])
        getText(r-1, c-1)
    else:
        if dp[r-1][c] > dp[r][c-1]:
            getText(r-1, c)
        else:
            getText(r, c-1)

getText(len(a), len(b))

for i in range(len(path) -1, -1, -1):
    print(path.pop(i), end = '')

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/9252.%E2%80%85LCS%E2%80%852

programmers/백준/Gold/9252. LCS 2 at main · ornni/programmers