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

그리디 / 실버 5

💵

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

14916번: 거스름돈

 

내 풀이

n = int(input())
ans = 0

while n > 0:
    if n == 1: # 거슬러 줄 수 없음
        ans = -1
        break
    if n % 5 == 0: # 5로 나누어 떨어짐
        ans += n // 5
        break
    else:
        n -= 2
        ans += 1

print(ans)

 

처음엔 5로 최대한 나누고 남은 값을 2로 나누는 방식을 생각했지만, 그렇게 하면 안 된다!

예를 들어, n = 13인 경우, 5원짜리 1개 + 2원짜리 3개의 조합이 정답이지만,

위의 방법을 사용하면 5원짜리로 두 번 나누고 남은 3원이 2원으로 나누어 떨어지지 않기 때문에 잘못된 값이 나온다.

 

즉, 5의 배수가 될 때까지 2를 빼주어야 한다.

 

 

 

거슬러줄 수 없는 경우를 빼먹어서 첫 제출 때 틀렸었다.

n이 음수인 경우로 처리하시는 분들도 계시던데, 나는 n = 1인 경우로 처리했다.