[그리디] 이코테 3-1. 거스름돈 (백준의 동전문제)

이코테 : 이것이 취업을 위한 코딩테스트다 책의 예제문제 풀이

문제

10의 배수로 주어지는 거스름돈을 돌려주려고 할 때, 최소 몇 개의 동전으로 거슬러 줄 수 있는가?
백준의 유사 문제인 11047 동전 포스팅

해설

가장 큰 동전으로 거슬러 줄 수 있는 금액부터 제거해줘야 최소 개수가 보장된다.
딕셔너리를 활용해봤다. 엊그제 해본 dic.items()의 sum도 써봤다.

코드

coins = [500, 100, 50, 10]
coins.sort(reverse=True)
n = int(input()) # 거스름돈
# 줄 동전의 최소 개수
cnt = 0
dic = {}
for c in coins:
    dic[c] = n//c
    n -= dic[c]*c
    # print(n)

print(sum(v for i,v in dic.items()))

마지막줄의 v for i, v - 를 sum(i/*v for i, v in dic.items()) 가 되면 처음 입력되는 값이 출력된다.