[백준] 11047번 동전 0(python)

문제)

알고리즘)

그리디 알고리즘 대표적인 문제

-동전을 내림차순으로 정렬

-큰값부터 차례로 나눠준다 (나눌때 몫을 카운트)

 동전 수 출력

코드)

#다시 풀이
# 동전0
import sys
from collections import deque
input = sys.stdin.readline

cnt, price = map(int, input().split())
result = 0
coin = []
for _ in range(cnt):
    coin.append(int(input()))

coin.sort(reverse= True)

coin = deque(coin)
while coin:
    current = coin.popleft()
    if current > price:
        continue

    result += (price//current)
    price %= current


print(result)