백준 14916번 거스름돈 풀이 및 정답(python)

 

 

---

문제 설명

주어진 금액을 5원과 2원짜리 동전을 가지고

최소의 동전으로 거슬러 주는 문제입니다.

 

풀이

5원을 가장 많이 쓰는 방향을 찾아야합니다.

주어지는 수를 5원으로 나눈 뒤 2원으로 나눠지는 값이 있는지 찾습니다.

 

예를 들어 21원인 경우

5원으로 4개, 2원으로 나눌 수 없음

5원으로 3개, 2원로 거슬러 줄 수 있음 <= 해당 케이스가 정답이 됩니다.

---

정답 예시 코드

givenMoney = int(input())

maxValue = givenMoney // 5
fiveCoin = maxValue

while fiveCoin >= 0:
    remain = givenMoney - (fiveCoin * 5)
    if (remain % 2) == 0:
        print(fiveCoin + (remain // 2))
        break
    fiveCoin -= 1
    
if fiveCoin == -1:
    print(-1)