11047: 동전 0

 

문제 접근

탐욕적 기법의 대표문제로 볼 수 있는 동전 문제이다. 예전에 풀었던 문제라 수월하게 풀었다. 가장 값이 비싼 동전부터 사용해서 전체 금액을 모두 차감하는 식으로 구성하면 된다. 

import sys

n, k = map(int, sys.stdin.readline().split())
coins = []
for i in range(n):
    coin = int(sys.stdin.readline())
    coins.append(coin)
i = 0
cnt = 0
while k:
    big_coin = coins[-(1 + i)]
    cnt += k // big_coin
    k = k % big_coin
    i += 1
print(cnt)