백준 - 14916 - 거스름돈 [파이썬]

개발일지 쓰는 건 재밌다.

이제 두번째라 그런가 아니면 짤을 올릴 수 있다는 생각때문인가

짤 올릴거임 메롱

 

1. 문제

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

14916번: 거스름돈

문제분류 :  그리디 알고리즘

그리디 알고리즘의 대표적인 유형.

 

2. 이해 및 풀이

처음에는 냅다 빼서 횟수를 구해볼까도 싶었는데 아참참,

그리디 알고리즘이 성립하려면, 약수배수의 관계를 가져야 한다.

 

5원을 빼줄만큼 뺐을 때 남은 수가 2의 배수여야 한다.

만약에 남은 수가 2의 배수(짝수)가 아니라면?

=> 5원입장: 빼줄만큼 빼준 횟수-1, 2원입장: (빼줄만큼 뺀 수+5)에서 2를 나눠주면 된다.

(참고) 빼줄만큼 뺀 수(홀수)+5(홀수)는 짝수!!

money = int(input())
    
m= money%5
 
#거슬러줄 수 없는 경우(1원, 3원)
if money == 1 or money == 3:
    print(-1)

#5원 최대한 빼고난 후의 수가 짝수일 경우
elif m%2 ==0:
    print(money//5 + m//2)
          
#5원 최대한 빼고난 후의 수가 홀수일 경우
elif m%2 ==1:
    print((money//5-1)+(m+5)//2)