백준, 동전 0, 11047, 파이썬

[유형]

그리디 

 

[문제링크]

https://www.acmicpc.net/problem/11047

 

[요약]

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

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

 

[문제풀이]

coins의 리스트 안에서 M으로 나눌 수 있는 가장 큰 수를 찾는다.

몫은 answer에 더해주고 나머지는 M에 부여한다.

import sys
from collections import Counter
def input():
    return sys.stdin.readline().rstrip()

N, M = map(int, input().split())
coins = []
for _ in range(N):
    coins.append(int(input()))

coins.sort(reverse=True)

answer = 0

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