[백준] 9251번 : LCS (python 파이썬)

👉 9251번 : LCS



✍ 내 코드


# 골드 5레벨        LCS
from sys import stdin

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

for x in range(1, len(str2) + 1):
    for y in range(1, len(str1) + 1):
        if str1[y - 1] == str2[x - 1]:
            dp[x][y] = dp[x - 1][y - 1] + 1
        else:
            dp[x][y] = max(dp[x - 1][y], dp[x][y - 1])
print(dp[len(str2)][len(str1)])


✍ 팁

  • 다이나믹 프로그래밍을 이용해서 하나의 문자열에 다른 하나의 문자열을 한글자씩늘려가면 같은게 얼마나 있는지 체크하는 것 이다.

좋은 웹페이지 즐겨찾기