[BOJ][Python][골5][9251] LCS

문제 링크

문제링크

첫 번째 풀이

정답 코드

LCS를 구하는 방법은 여기에 잘 정리되어 있습니다.

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
from operator import itemgetter

# sys.stdin = open("input.txt", "r")
s1 = input()
s2 = input()
s1 = '0' + s1
s2 = '0' + s2
R, C = len(s1), len(s2)
dp = [[0] * C for _ in range(R)]
# dp = [[[0] * K for _ in range(C)] for _ in range(R)]
# MOD = 1000000000

for r in range(1, R):
    for c in range(1, C):
        if s1[r] == s2[c]:
            dp[r][c] = dp[r - 1][c - 1] + 1
        else:
            dp[r][c] = max(dp[r - 1][c], dp[r][c - 1])

print(dp[R-1][C-1])

Success Notice: 수고하셨습니다.