[백준] 11047 동전0 파이썬 풀이 (그리디)

문제

• k원을 만드는데 필요한 동전 개수의 최솟값을 출력하라

 

문제 풀이

• 입력받은 코인을 배열에 저장하고 내림차순으로 정렬한다.
• k원보다 코인이 큰 것은 지나가고 k원보다 작아지면 k원을 coin으로 나눌 수 있는 지 확인한다
• 나눌 수 있으면 몫이 coin의 개수이고
• 나머지가 남으면 나머지를 다음으로 작은 코인으로 나눈 것을 더하면 된다.

 

 

 

코드

 

import sys
kind_of_coin, money = map(int,sys.stdin.readline().split())
coins = []
for _ in range(kind_of_coin):
    coin = int(sys.stdin.readline())
    coins.append(coin)
 
coins.reverse()
count = 0
for i in range(kind_of_coin):
    if coins[i]<= money:
        count += money//coins[i]
        money = money%coins[i]
print(count)