[백준] 2839번 설탕 배달 해설 및 풀이 (Python)

백준 2839번 설탕 배달

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

---

 

문제 유형

수학
다이나믹 프로그래밍
그리디 알고리즘

 

풀이 방법 도출

우선 그리디하게 5kg 봉지를 최대한 많이 사용하고, 나머지를 3kg 봉지로 채우는 방법이 최적입니다.

1. 5kg 봉지를 많이 쓰지만 남은 무게가 3으로 나누어떨어지는지 확인합니다.
2. 나누어서 떨어지면 해당 조합이 최소 봉지 수일 수 있으므로 출력합니다.
3. 아니라면 5kg 봉지 하나를 줄이고 다시 시도합니다.
4. 끝까지 되지 않으면 -1 출력합니다.

 

시간 복잡도

• 반복문 : O(N)

 

---

 

핵심 코드 삽입 및 설명

n = int(input())

# 5kg 봉지를 최대한 많이 사용하는 방향으로 반복
count = -1  # 초기값을 정확히 나눌 수 없는 경우 -1로 설정
for five_bag in range(n // 5, -1, -1):  # 5kg 봉지를 많이 쓰는 방향으로 감소
    remain = n - (5 * five_bag)  # 5kg을 썼을 때 남는 무게
    if remain % 3 == 0:
        three_bag = remain // 3
        count = five_bag + three_bag  # 전체 봉지 수
        break  # 최소 봉지이므로 더 이상 볼 필요 없음

print(count)