[백준] 11047. 동전0 - python, greedy

11047 동전0

풀이

• 동전이 이미 오름차순으로 정렬되어 있기 때문에 이를 거꾸로 정렬해준다.
• 이는 동전이 가장 큰 것부터 소거해야 가장 최소가 되는 수를 찾을 수 있기 때문이다.
• 그 이후에는 몫과 나머지를 이용하여 연산을 수행해주면 된다.

import sys

sys.stdin = open("11047_동전0_input.txt", "r")
n, k = list(map(int, sys.stdin.readline().split()))
coins = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
cnt = 0
coins.reverse()

for v in range(n):
    count += k//coins[v]
    k = k % coins[v]
print(count)