[Boj] 백준 동전0 11047(python)

문제링크 : https://www.acmicpc.net/problem/11047

동전의 갯수와 목표 금액을 입력받은 후, 동전 금액이 한 줄씩 입력됨

동전 금액이 작은 동전 금액의 배수 관계가 성립하므로 그리디로 접근 가능

큰 동전 금액 기준으로 동전을 거슬러주면 됨

import sys

n, money = list(map(int, input().split()))
coins = []
answer = 0
for i in range(n):
    coin = int(sys.stdin.readline())
    coins.append(coin)

coins.sort(reverse=True)

for coin in coins:
    if money // coin > 0:
        answer += money // coin
        money = money % coin
print(answer)