[PS] 백준 9251 LCS

문제

BJ 9251 LCS
문제 분류 : DP
문제 난이도 : 골드 5

문제 코드

import sys
from collections import deque

input = sys.stdin.readline

str1 = list(input().strip())
str2 = list(input().strip())

# 풀이 1

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

for i in range(1, len(str1) + 1):
    for j in range(1, len(str2) + 1):

        if str1[i - 1] == str2[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[-1][-1])

#######################

# 풀이2

dp = [0] * len(str2)

for i in range(len(str1)):
    cnt = 0

    for j in range(len(str2)):
        if cnt < dp[j]:
            cnt = dp[j]
        elif str1[i] == str2[j]:
            dp[j] = cnt + 1

print(max(dp))

문제 복기 & 느낀점

받아들이기 정말 힘든 문제였다.. 당연히 풀지 못했고, 구글링해서 풀이를 이해해보려고 해도 도무지 받아들여지지 않았다.

코드를 따라가면서 '아! 이런 원리구나!' 라는 생각이 들어도,
'실전에서 이 점화식을 유추해낼 수 있을까?'라는 막연함이 더 컸다.

https://myjamong.tistory.com/317
위의 글을 참고해서 꾸역꾸역 이해했다.. 결국 느낀 점은 점화식에 직관적으로 이해하고 유추하기 보다는 dp 테이블을 만들어서 하나하나 써보고 케이스를 따져보면서 '발견'하는 것이 중요하지 않을까 싶다. 적어도 아직까지 내 실력에서는 말이다...