[백준] q11047 동전 0

문제

주어진 동전들을 적절히 사용해서 그 가치의 값을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하라.

어떻게 풀 것인가?

‘가장 큰 화폐 단위부터’ 사용한다. 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 사용하여 가치의 합을 K로 만드는 작업을 수행한다.

# N, K를 공백으로 구분하여 입력받기
n, k = map(int, input().split())
# n개의 수를 입력받기
coin_types = []
count = 0
for _ in range(n):
    coin_types.append(int(input()))

coin_types.sort(reverse=True)  # 입력받은 수들 내림차순 정렬하기

for coin in coin_types:
    count += k // coin  # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    k %= coin

print(count)