1. 문제

출처: 백준 9251번 LCS

2. 풀이

주어진 문자열을 쪼개서 끝자리를 하나식 비교해나가는 과정으로 DP 표를 만들고 풀이할 수 있다.

아래 그림은 주어진 예제의 DP 표를 만드는 과정을 그린 것이다.

3. 소스코드

word1 = input()
word2 = input()

dp = [[0]*(len(word1)+1) for _ in range(len(word2)+1)]

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

4. 그 외