백준 11047번 동전 0 [그리드 알고리즘]

백준 11047번 동전 0

백준 11047번 동전 0는 주어진 동전의 타입들을 활용해서 주어진 값을 만드는데 최소한의 동전의 수를 사용해서 주어진 값을 만든다.

즉 "N개의 동전 종류가 주어지고, 합이 K가 되도록 할 때의 필요한 동전 개수의 최소 값을 구하는 것이다."

 

[문제풀이과정]

1.  주어진 동전에서 최소한의 동전의 수를 구하기 위해서는 크게 나누어 줄 수 있는 동전부터 사용하는게 적절함.

2. 동전을 큰 값부터 정렬

3. 동전의 단위가 배수의 형태를 가지고 있기 때문에, 그리디 알고리즘의 최적해를 보장한다.

 

[코드]

count, price = map(int,input().split())
coins = [int(input()) for _ in range(count)]

result = 0
for coin in coins[::-1]:
    if price == 0:
        break
    
    if price // coin > 0 :
        result += price//coin
        price %= coin
        
print(result)