[백준] 설탕 배달

문제_

https://www.acmicpc.net/problem/2839
실버 IV

풀이_

1. 3kg봉지보다는 되도록 5kg봉지를 쓰는 게 무조건 적은 개수가 된다.
   • 예: 15kg 설탕은 3kg로 배달하면 5개가 나오지만, 5kg로 배달하면 3봉지로 나온다
2. 5kg로 담을 수 없는 경우, 3kg봉지를 이용해 담도록 한다.
   • 8kg를 넘어가면 모든 수를 5kg와 3kg로 표현이 가능하다. (1=5x2-3x3, 2=5-3)
3. 즉 5kg로 최대한 담고 남은 게 있으면 5kg 봉지를 줄여가며 3kg으로 표현이 가능한지 확인한다.
   • 지금 시점에서 최선의 선택을 하다: Greedy

n = int(input())

def solution(n):
  return -1 if n < 8 and not(n % 3 == 0 or n % 5 == 0):
    return -1
  count = n // 5
  n = n % 5

  while n % 3 != 0:
    count -= 1
    n += 5
  count += n // 3
  return count

print(solution(n))