11047 동전 0

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

#그리디

11047번: 동전 0

#그리디

각 상황에서 최적의 해를 구하는 것이 전체의 해를 구하는 것에서의 최적이 되게끔 하는 알고리즘

 

#코드

#11047 동전 0

 

n,k=map(int,input().split())

coins=[int(input()) for i in range(n)]

#입력

 

coins.reverse()

#동전의 최솟값을 구할 것이기 때문에 큰것부터 비교해야 한다.

answer=0

for coin in coins:

if coin<=k:

answer+=k//coin

#몫은 동전의 개수가 되고

k=k%coin

#나머지는 그 동전을 뺀 나머지가 된다.

print(answer)

 

#동전 시리즈의 막내, 그리디는 반복된다는 생각말고 일단 그 해만 해결해보자는 생각으로 하는게 편한 것 같다.