알고리즘: 백준 11047번 동전0 (feat.Python)

 

4200원을 만드는데 필요한 동전의 갯수가 최소가 되게하기 위해선

 

가장 큰 동전으로 나누어 나가면 된다.

 

4200원 다음으로 가장 동전은 1000원이므로 

 

4200 // 1000 = 4 ... 200

200 //100 = 2 ... 0

 

이므로 4 + 2 = 6이다. 

 

 

import sys

input = sys.stdin.readline

n, k = map(int, input().split())

money_list = []

for i in range(n):
    money_list.append(int(input()))


change_count = 0

for i in range(n - 1, - 1, -1):

    if k == 0:
        break
    tmp = (k // money_list[i])
    change_count += tmp
    k %= money_list[i]


print(change_count)

 

10 4200
1
5
10
50
100
500
1000
5000
10000
50000
6

Process finished with exit code 0