[다이나믹 프로그래밍] 백준 2839번: 설탕 배달

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

2839번: 설탕 배달

import sys
n = int(input())

inf = sys.maxsize
dp = {}
dp[-2] = inf
dp[-1] = inf
dp[0] = inf
dp[1] = inf
dp[2] = inf
dp[3] = 1
dp[4] = inf
dp[5] = 1

for i in range(3,n+1):
    if i not in dp:
        dp[i] = min(dp[i-3], dp[i-5]) +1

if dp[n] >= inf: # dp[n]이 inf+1일 수도 있음, 그래서 등호로 하면 안됨
    print(-1)
else:
    print(dp[n])

배운점

 - 발상이 안되면 정말 어려운 문제이기 때문에 이러한 방법론 자체를 기억해놓는게 좋다.

 - 코드의 아래쪽 부분에서 inf+1을 생각못하고 dp[n]== inf로 비교하다가 계속 틀렸다. 예외 주의!