BOJ11047 - 동전0

문제11047

문제

• 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

• 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

해결

• 동전 문제는 가장 큰 금액 부터 계산 해주면 최솟값의 조건을 맞출수 있다.

answer = 0
n,k = map(int,input().split())
moneys = []
for _ in range(n):
    moneys.append(int(input()))

moneys.sort(reverse=True)

for m in moneys:
    if k < m:
        continue

    answer = answer + (k // m)
    k = k % m

print(answer)