백준 / 설탕 배달 / 2839번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 설탕 배달 / 2839번 (실버 4단계) 

문제 사이트: https://www.acmicpc.net/problem/2839

 

문제 설명

---

나의 풀이

sugar = int(input())

bag = 0

while sugar >= 0:
    if sugar % 5 == 0:
        bag += (sugar // 5)
        print(bag)
        break
    sugar -= 3
    bag += 1
if sugar < 0:
    print(-1)

---

※ 알아야 할 것

def sugar_delivery(sugar):
    # DP 테이블 초기화
    dp = [float('inf')] * (sugar + 1)
    dp[0] = 0  # 0kg는 봉지가 필요 없음

    # DP 테이블 채우기
    for i in range(1, sugar + 1):
        if i >= 3:
            dp[i] = min(dp[i], dp[i - 3] + 1)
        if i >= 5:
            dp[i] = min(dp[i], dp[i - 5] + 1)

    # 결과 반환
    return dp[sugar] if dp[sugar] != float('inf') else -1

# 입력
sugar = int(input())
print(sugar_delivery(sugar))

DP를 이용하여 푸는 방법도 있다.