[백준] 2839번 설탕 배달(with python)

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

2839번: 설탕 배달

 

1. 정답 코드

n = int(input())
cnt = 0

while n >= 0:
  if n % 5 == 0: #5로 나누어 떨어질경우 
    cnt += (n//5)
    print(cnt)
    break
  n -= 3 #5로 나누어 떨어지지 않으면 3을 반복해서 빼준다
  cnt += 1
else: #5와 3 둘 다 나누어 떨어지지 않을 경우 -1 출력
  print(-1)

한 시간 정도 고민을 하다가 도저히,, 안되겠어서,, 구글링

 

이 문제는 greedy 알고리즘을 이용하는 문제이다.

 

5의 횟수가 많으면 많을 수록 좋으나, 3의 배수가 더해져 있을 때를 고려해야한다.

 

아으 어려워ㅠ