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

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

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net

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로 비교하다가 계속 틀렸다. 예외 주의!