코드

n = int(input())

# 동전 종류
coin = [500, 100, 50, 10, 5, 1]

# 구현 기능
def solution(n, coin):
    # 받을 거스름돈
    change = 1000 - n

    # 거스름돈으로 받은 잔돈의 개수
    cnt = 0
    
    # 잔돈 종류별로 반복
    for c in coin:

        # 남은 돈이 현재 잔돈보다 작아질 때까지 반복
        while change >= c:
            
            # 거스름돈에 현재 잔돈 금액만큼 빼줌
            change -= c
            
            # 잔돈을 한 번 계산했으므로 cnt + 1
            cnt += 1
        
    print(cnt)        
    
solution(n, coin)

문제 해설

대표적인 그리디 알고리즘 문제.

동전의 종류가 서로 약수 관계이고, 내림차순 정렬돼있으므로 큰 동전부터 하나씩 거스름돈에 금액에 맞게 감소시키면서 감소시킬 때 마다 1개씩 숫자를 세어주면 정답을 구할 수 있다.

댓글남기기

참고