[백준 11047] 파이썬 동전 0

그리디 알고리즘을 사용해서 문제를 풀이했다. 그리디 알고리즘문제이기 때문에 ..

 

오름차순으로 동전의 가치가 주어지므로 동전 개수의 최솟값을 구하기 위해서는 최대한 비싼 동전을 써야한다.

따라서 리스트에 동전을 하나씩 추가해주고 뒤에서부터 조회하며 준규의 동전에서 빼줬다.

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


for i in range(len(coin)-1,-1,-1):
    count += k // coin[i]
    k = k - k // coin[i] * coin[i]
    
print(count)