[백준] 2839 설탕 배달 (feat.DP) (python 파이썬)

2839번: 설탕 배달

---

설탕 N킬로그램을 주고 이걸 5킬로그램, 3킬로그램 봉지로 가장 적은 개수로 나누는 문제. 처음에는 수학으로 해결하려다가 "동전" 문제가 생각나서 DP로 해결했다. 

---

아이디어

n킬로그램은 (n - 3) + 3 또는 (n - 5) + 5로 생각할 수 있다.

따라서 n킬로그램의 봉지 개수는 n - 3과 n - 5 킬로그램 봉지 개수 중 작은 거(min) + 1이 된다.

 

이 아이디어로 해결하려면 n - 3과 n - 5의 개수 정보를 저장해 뒀다가 재사용이 필요하다.

3 ~ n킬로그램까지 봉지의 최소 개수를 담을 리스트를 선언해서 해결하면 된다(DP).

---

전체 코드

N = int(input())

INF = int(10e9)
DP = [INF] * (5001)

DP[3] = 1
DP[5] = 1

for i in range(6, N + 1):
        DP[i] = min(DP[i - 3], DP[i - 5]) + 1

if DP[N] < INF:
    print(DP[N])
else:
    print(-1)

---

코드 설명

알고리즘은 아이디어 설명과 같다.

min 메서드를 쓰기 위해 리스트를 INF값으로 초기화해 준다.

 

예를 들어 N = 10이면 DP[7]과 DP[5]를 비교한다. 이때 봉지로 7 킬로그램을 만드는 경우는 없으니까 DP[7] = INF,

따라서 DP[10] = DP[5] + 1이 된다.

 

 

마지막 출력할 때 DP[N]값이 INF보다 크면 -1, 작다면 DP[N]값을 출력해 준다.