[Python] 설탕 배달 - 백준 (DP)

해당 글은 백준 2839번 문제 '설탕 배달'을 다룬다.

문제

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

2839번: 설탕 배달

 

설명

DP 문제로 거스름돈 최소갯수를 구하는 방법대로 구하였다.

dp[j] = min(dp[j], dp[j-3]+1, dp[j-5]+1) 식으로 구하면 된다. 출력할 때 dp[n] 값이 5001이상이라면 -1을 출력해준다.

 

코드

n = int(input())
dp = [5001]*5001
dp[0]=0
arr = [3, 5]
for i in arr:
    for j in range(i, n+1):
        dp[j] = min(dp[j], dp[j-i]+1)

if dp[n] >= 5001:
    print(-1)
else:
    print(dp[n])