Problem Solving/Dynamic Programming

[다이나믹 프로그래밍] 백준 9251번: LCS / 골드 5

by ggyongi 2021. 7. 23.

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

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

str1 = input()
str2 = input()

dp = [[0]*(len(str1)+1) for x in range(len(str2)+1)]

for i in range(1, len(str2)+1):
    for j in range(1, len(str1)+1):
        if str1[j-1] == str2[i-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[-1][-1])

다이나믹 프로그래밍인 줄 몰랐을 때 전혀 감이 안오다가

다이나믹 프로그래밍 쪽으로 생각해보니 점점 감이 왔다.

표를 그려보고 규칙을 찾아 코드를 작성하였다.

왜 되는지는... 정확힌 모르겠네..