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

알고리즘: 그리디 알고리즘 

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

---

풀이

가능한 동전을 작게 사용하여 거스름돈을 주는 문제입니다. 

가장 큰 액수의 동전을 먼저 사용해 액수를 채워주고 점차 작은 동전으로 거슬러줍니다. 

 

사용가능한 동전의 종류를 내림차순으로 정렬을 해줍니다. 

동전 중 총액보다 적은 액수의 동전만 거스름돈으로 사용할 수 있으므로

동전의 배열 coins에서 처음으로 거슬러줘야하는 돈보다 액수가 같거나 작은 동전이 나올 때의

인덱스를 기억해서 이를 통해 새 배열을 만들어줍니다 

 

이 배열은 액수의 내림차순으로 정렬되어 있으므로, 

하나씩 꺼내어 거슬러주며 남은 거스름 reamin을 업데이트 합니다. 

 

이때, 거슬러준 동전의 갯수만큼 cnt를 추가해주면 됩니다 

 

import sys 

N, remain_ = map(int,input().split(" "))
#동전의 갯수와 거슬러줘야하는 돈을 받습니다 
coins =[]

for i in range(N):
    coins.append(int(input()))
coins = sorted(coins, reverse =True)
#동전의 액면가를 배열에 추가해줍니다. 
stop =0 

for coin in coins: 
    if coin<=remain:
        stop=coins.index(coin)
        break 
#처음으로 액수가 거스름돈보다 작거나 같은 동전의 index를 받습니다 
#아래에서 동전의 배열을 이를 통해 슬라이싱을 하는데 
#거스름돈보다 액수가 적은 동전들로만 이루어진 배열을 구할 수 있습니다. 
coins= coins[stop:]
i=0
sum_num_coins= 0 
#동전을 하나씩 꺼내어보면서 최대한 많은 액수를 거슬러줍니다. 
#액수가 큰 것 -> 작은 것으로 거슬러줍니다
#이 과정에서 사용한 동전의 갯수(거스름돈(remain)//사용한 동전의 액수(coin[i])를 
#cnt에 업데이트 해줍니다
while sum_ != 0:
    num_coins =remain//coins[i]
    sum_=sum_-coins[i]*num_coins
    i= i+1 
    sum_num_coins+=num_coins

print(sum_num_coins)