[백준/Pyhton] 14916번: 거스름돈 (그리디 알고리즘)

1. 문제 

14916번: 거스름돈

어렵지 않은 실버5 문제였으나 그리디 알고리즘을 복기하기에 좋은 것 같아 포스팅 해본다 ! 

 

2. 풀이 

그리디는 정말 간단하게 생각해보는게 답인 것 같다. 

우선 받을 수 있는 거스름돈의 동전은 2, 5원이다. 그렇다면 1,3,..등 2,5로만 이루어지지 않는 수는 -1을 출력해주어야한다.

 

1) 우선 5로 나누어보고 5로 나누어떨어지지 않는다면 

2) 2를 감해준다. 그리고다시 1)번으로 되돌아간다. 

 

1) - 2)를 반복해주고 n이 0보다 작다면 불가능한 경우인(-1)을 출력해주고, n==0으로 나누어떨어진다면 답인 (ans)를 출력해준다 ! 

 

3. 코드 

n = int(input())
# 동전의 개수
ans = 0

while (1):
    if n%5 == 0:
        ans+= n//5
        break
    else:
        n-=2
        ans+=1
    # n이 0또는 5의 배수가 아니라면 다시 while문으로 들어감 

# n이 2와 5의 조합으로 나누어 떨어지지 않는 경우
if n<0:
    print(-1)
# n이 2와 5의 조합으로 나누어 떨어지는 경우
else:
    print(ans)