Algorithm
[백준 2839] 설탕 배달
MingyuPark
2022. 9. 13. 14:30
문제
https://www.acmicpc.net/problem/2839
2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
아이디어
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)