백준 알고리즘 11047번 동전 0(python)

K보다 싼 동전 중에서 제일 큰 것부터 순서대로 꽉꽉 채운다는 느낌으로 풀면 된다.

EX) K = 4200, 입력: 1 5 10 50 100 500 1000 5000 10000 50000

ans = 0

1) 4200 - 1000*4 = 200 -> ans = 0 + 4 = 4

2) 200 - 100*2 = 0 -> ans = 4 + 2 = 6 -> 6 출력

N, K = map(int, input().split())
li = sorted([int(input()) for _ in range(N)], reverse=True)
cnt = 0
for c in li:
    if c <= K:
        cnt += K//c
        K %= c
    if K == 0:
        break
print(cnt)