BOJ 2839 설탕 배달 풀이

[allzeroyou]

문제 분석

첫 번째 단계(문제 요약 및 조건 파악)

설탕을 n킬로그램 배달

3, 5킬로그램 봉지 → 18킬로그램 설탕을 배달해야 할때

3킬로그램 봉지 6개를 가져가도 되지만

5킬로그램 봉지 3개 + 3킬로그램 봉지 1개가 더 효율적임.

설탕 배달 시 봉지 몇개 가져가면 되는지?

• 입력

첫째줄에 N이 주어짐(3 ≤ N ≤ 5000)

• 출력

봉지 최소 개수(만약, 정확하게 n킬로그램 만들 수 없다면 -1 출력)

두 번째 단계 (문제 핵심 파악)

n이 0이 될 때까지 반복문을 돌면서, 큰 수인 5로 나누고 5의 배수가 아니라면 3을 빼주고 봉투 개수를 증가시킨다. 위 과정을 반복하면서 n이 나눠떨어지지 않고 음수가 된다면 -1을 출력

코드 작성

import sys

input = sys.stdin.readline

n = int(input())
ans = 0 # 개수

while (n >= 0):
 if n % 5 == 0:
 ans += (n // 5)
 print(ans)
 break
 n -= 3 # 5의 배수가 아니라면 3을 빼준다.
 ans += 1
else:
 print(-1)

느낀점

그리디 알고리즘으로 매순간 가장 탐욕스러운 선택을 한다.

그러나 그리디는 최적의 해는 보장하지 않는다.