Python/Greedy BOJ-11047 동전0

Posted on | In

[Python/Greedy] BOJ-11047 동전0

📌문제링크


거스름돈과 유사하다. 화폐단위가 큰것부터 고려하여 문제를 풀면된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

N, K = map(int, input().split())
coin=[]
for _ in range(N):
    tmp = int(input())
    coin.append(tmp)

cnt =0
while 1 :
    for i in range(N-1,-1,-1):
        if K >= coin[i] :
            cnt += K//coin[i]
            K = K%coin[i]
    if K == 0 :
        break
print(cnt)