[알고리즘/파이썬] 백준 11047번 - 동전0

 

 

11047번: 동전 0

 

백준에서 그리디 알고리즘으로 분류된 문제. 매순간 최적의 답들을 구하다 보면 결국 결과도 최적의 값이 될거라는 접근법이다. 

 

주어진 금액K를 최소한의 동전을 이용해서 구해야한다. 동전의 가치가 가장 높은것을 먼저 사용(최적의 값)해서 K를 줄여나가면된다.

nk = list(map(int,input().split()))
k = nk[1]
coin = []

for _ in range(nk[0]):
    c = int(input())
    
    # 입력된 동전이 k보다 크면 k를 나눌수 없기때문에 제외시킴.
    if c <= k:
        coin.append(c)

c_cnt = 0

# 동전가치가 큰값부터 가져와서 나눈다.
for i in range(len(coin)-1, -1 , -1):
    c_cnt += int(k/coin[i])
    k = k%coin[i]
print(c_cnt)