동전 0 - 백준 11047번

동전 종류를 배열로 입력을 받는다.

오름차순으로 정렬되어있기 때문에 배열의 가장 끝인 배열[-1]의 값이 가장 큰 값이다. 

동전을 최소한으로 사용하여 K를 만들어야하기 때문에 K에서 큰 값을 하나씩 빼주면서 카운팅해준다.

배열에 들어있는 수 중 가장 큰 수가 K보다 크면 배열.pop() 으로 삭제해준다.

K값이 0이 될때까지 가능한한 큰 값의 동전으로 빼준다.

 

 

n, k = map(int, input().split())
coin = []
c=0
for _ in range(n):
    coin.append(int(input()))
while k>0:
    if coin[-1] <= k:

        r = k//coin[-1]
        k = k-coin[-1]*r
        c += r
        coin.pop()
        
    else:
        coin.pop()
        
print(c)

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