[python/백준] 14916. 거스름돈(S5)

📌 문제 탐색하기

👉 문제바로가기

n: 거스름돈 액수(1 ≤ n ≤ 100,000)
동전의 개수가 최소가 되어야 하므로 5로 나누어 떨어지면 5로 나눈 몫(5원의 갯수)을 출력하면 됩니다. 여기서 5로 나누어 떨어지지 않는 경우를 생각해봐야 하는데요, 이 경우 5로 나누어질때까지 반복해서 해당 숫자를 2씩 감소시키면 됩니다. 2씩 감소시킬때 카운트를 해줘서 5로 나눈 몫과 2만큼 몇 번 감소시켰는지 그 횟수를 더해주면 5원의 갯수와 2원의 갯수를 구할 수 있겠네요.

2씩 계속 감소시켰는데 5로 끝까지 나누어지지 않는다면 거슬러 줄 수 없는 경우가 됩니다.

📌 알고리즘 선택

그리디로 문제를 풀 수 있을지 판단하려면 각 단계의 최적해가 전체 문제의 최적해가 되는지 확인하면됩니다. 큰 금액의 동전부터 거슬러 줄 수 있는 최대 금액으로 거슬러주면 결국 전체 지급해야하는 동전 개수가 최소가 되니 그리디로 풀이가 가능하겠네요.

📌 코드 설계하기

1. 총 거스름돈 액수를 Input받습니다.
2. 5로 나누어 떨어질때까지 2원씩 빼면서 2원이 얼마나 있어야 거스름돈이 5의 배수가 되는지 구합니다.
3. 5원의 갯수와 2원의 갯수를 더해서 출력합니다. (이 때, n이 음수가 될 때까지 5원으로 나누어떨어지지 않는다면 거슬러 줄 수 없는 경우이므로 -1을 출력합니다.)

📌 시도 회차 수정 사항 (Optional)

시간초과

오답

📌 정답 코드

import sys

n = int(sys.stdin.readline()) #거스름돈 액수
count = 0  #2원의 갯수

while True:
    if n % 5 == 0:
        result = n // 5  #5원의 갯수
        break
    else:
        n -= 2
        count += 1  

if n < 0:
    print(-1)
else:
    print(result + count)            

📌 문제 총평