[백준_2502] 떡 먹는 호랑이 python

처음 이 문제를 접했을 때, dp인 것과 점화식은 너무 분명히 보였으나,

초기 값 설정을 어떻게 해야 할지 고민에 빠졌다.

 

dp[d-1]부터 역추적을 해야 하나 했으나,

수가 그렇게 많지 않아 전수조사를 해도 나쁘지 않겠다는 아이디어가 떠올랐다.

초기값 설정이 불가능한 dp이므로 리커전을 사용하여 모든 케이스를 조사한다.

d, k = map(int, input().split())

dp = [

　0 for _ in range(31)

]

for i in range(1, k):

 

　for j in range(i, k):

 

　　dp[1] = i

　　dp[2] = j

 

　　for h in range(3, d + 1):

　　　dp[h] = dp[h-1] + dp[h-2]

　　　if dp[d] == k:

　　　　print(dp[1])

　　　　print(dp[2])

　　　　quit()

 

　　dp = [

　　0 for _ in range(31)

 

　　]