백준 2839번 - 설탕 배달 파이썬

📌 백준 2839번 - 설탕 배달 (DP)

✨ 문제 요약

당신은 설탕을 정확히 N킬로그램 배달해야 합니다.
설탕 봉지는 3kg 또는 5kg 두 종류만 있습니다.
가장 적은 봉지 수로 N킬로그램을 배달하려면 몇 개가 필요할까요?
만약 정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다.

---

🧠 문제 해석

• 3kg, 5kg 봉지만 사용 가능
• 조합해서 정확히 N을 만들어야 함
• 최소 봉지 수를 구하는 문제 → 최소값 DP

---

🔧 점화식 설계

dp[i] = i킬로그램을 만들기 위한 최소 봉지 수

기본 점화식:

dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1)

• i-3에 3kg 하나 추가
• i-5에 5kg 하나 추가
• 둘 중 최소값 선택

초기값:

• dp[0] = 0 (0kg은 봉지 0개)
• 나머지는 float('inf')로 설정 (도달 불가 상태)

---

✅ 정답 코드 (Python)

N = int(input())
dp = [float('inf')] * (N + 1)
dp[0] = 0
if N >= 3:
    dp[3] = 1
if N >= 5:
    dp[5] = 1

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

if dp[N] != float('inf'):
    print(dp[N])
else:
    print(-1)

---

🧱 DP 테이블 예시

N dp[N] 의미

3	1	3kg 1개
4	∞	불가능
5	1	5kg 1개
6	2	3kg 2개
7	∞	불가능
8	2	5kg 1개 + 3kg 1개
9	3	3kg 3개
10	2	5kg 2개

---

🧩 배운 점

• 최소값 문제는 보통 초기값을 무한대로 설정
• dp[0] = 0을 기반으로 누적 계산
• 목표가 도달 불가면 float('inf') 상태 그대로 남음 → 예외 처리 필요
• 봉지 단위가 고정된 경우는 그리디로도 가능하지만, DP가 더 일반적

---

🎓 정리

항목 설명

문제 유형	DP (최소 조합)
점화식	dp[i] = min(dp[i-3]+1, dp[i-5]+1)
초기값	dp[0] = 0, 나머지는 무한대
예외처리	dp[N] == inf → -1 출력

---

🏷 해시태그

#DP #설탕배달 #백준2839
#최소봉지수 #3kg5kg #동적계획법
#파이썬DP #백준Python #알고리즘공부