[백준] 14916 : 거스름돈 - Python

문제해결
이 문제의 경우 그리디, dp 모두 해결가능
이번에는 그리디로 풀어보았다.
문제에서 거스름돈을 2,5원으로만 거슬러줘야한다. 2,5원 각각은 배수관계가 아니라 따로 생각해줘야 하고 동전의 개수가 최소개수로 거슬러 줘야 하므로 최대한 5원을 사용하는 것이 좋다. 그렇기에 5의 배수라면 5원으로 다 주고 그게 아니라면 2원씩 빼면서 5의 배수가 될 때까지 진행...

생각
그리디에서 탐욕법을 생각하면 쉽다.

소스코드

import sys


#2, 5원짜리로만 거스름돈
#동전개수 최소
N = int(input())

count = 0
while N > 0:
    if N % 5 == 0:
        count += N // 5
        break
    else:
        N -= 2     #5의 배수가 아니면 2원씩 빼서 5로 나누어떨어지는 것이 나올 때까지.
        count += 1
    
#반복문 탈출 후 0보다 작을 수도
if N < 0:
    print(-1)   #음수면 거슬러줄 수 없으니
else:
    print(count)