[백준 2839] 설탕 배달

문제

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

2839번: 설탕 배달

---

아이디어

N킬로그램에서 필요한 봉지의 수를 f(N)이라고 하자.

이 경우 봉지를 하나 추가하는 경우는 3kg 봉지를 하나 추가하는 경우와 5kg 봉지를 하나 추가하는 경우 둘 중 하나이다. 

즉, f(N) = f(N-3) + 1이거나 f(N) = f(N-5) + 1이 될 수 있다. 

 

f(N-3)과 f(N-5)의 대소관계를 비교해야 한다. 봉지 수가 가장 적은 경우를 구해야 하기 때문에 f(N-3)과 f(N-5) 중 봉지 수가 더 적은 경우에 1을 더해야 한다. 즉 f(N) = min(f(N-3), f(N-5)) + 1이다. 

 

DP를 이용해 메모이제이션 기법을 통해 각 N에 대한 f(N)값을 저장하여 점화식으로 계산할 수 있다. 

 

주의할 점은 리스트를 초기화할때 f(N)을 0또는 문제에 맞춰 -1로 초기화하는 경우 이 값이 최솟값이 되기 때문에 N킬로그램을 만들 수 있는 방법이 없는 경우를 큰 수(10,000)로 설정한 후, 출력만 -1로 하는 기법을 선택했다. 

---

Solution

 

n = int(input())

cache = [10000 for _ in range(5001)]
cache[3] = 1 
cache[5] = 1 

for idx in range(6, 5001) : 
    cache[idx] = min(cache[idx-3], cache[idx-5]) + 1
    
print(cache[n] if cache[n] < 10000 else -1)