[Python] 백준 11047: 동전 0

 

n, k = map(int, input().split())
coin = []
for i in range(n) :
    coin.append(int(input()))

coin.sort(reverse = True)
count = 0

for i in coin :
    if (k == 0):
        break
    else :
        count += k // i
        k -= i * (k//i)

print(count)

 

coin 을 내림차순으로 정렬한 후, 단위가 큰 동전부터 계산한다.

동전을 k로 나눈 몫이 그 동전이 필요한 개수이다.

계산이 된 만큼 K를 감소시키다가, 0 이 되면 동전으로 K를 다 만든 셈이므로 반복문을 탈출한다.