[백준 11047] 동전 0 / 파이썬 + 그리디 알고리즘

동전을 적절히 사용하여 가치의 합을 K로 만들 때, 필요한 동전 개수의 최솟값을 구하는 코드를 짜는 문제이다.
알고리즘 분류는 그리디 알고리즘이라고 한다.

그리디 알고리즘

당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 (ex. 단순하게 큰 경우만 쫓음)
항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [ int(input()) for _ in range(n) ]
coins.sort(reverse=True)
count = 0

for coin in coins:
    if coin > k:
        continue
    count += k // coin
    k %= coin
print(count)