문제

흔히 아는 동전 그리디 문제이다

입출력 예시

해설

가격이 주어지면, 큰 동전들 중에서 주어진 가격 이하인 값을 나눠서 몫을 동전의 개수로 하고, 나머지를 남은 가격으로 해서 반복하여 나누기 작업을 하면 된다.

예)
4200원 받음-> 동전은 1000원, 500원, 100원이 있음-> 가격에 가장 인접한 1000원으로 나누면 4가 나옴->일단 개수는 4개임->나머지는 200원임->200원에 가장 인접한 100원으로 나누면 2개 나옴->동전 개수4개에 2개 더해서 6개임->나머지는 0원임->끝

코드

# 백준 11047 동전 0 / 실버4 / 그리디
import sys

# 동전의 종류 N과 가격K
N, K = map(int, sys.stdin.readline().split())

# coins
coins = []

# 동전 가격 입력
for i in range(N):
    coins.append(int(sys.stdin.readline())) 

# 그리디 시작
# K원을 만드는 데 필요한 최소한의 동전 개수는?
num_of_coins = 0 # 동전 개수
for coin in coins[ : : -1]: #큰 동전부터(내림차순)
    if coin <= K: #동전가격이 K보다 이하일 때만
        #print("coin: ", coin)
        num_of_coins += K // coin #동전 개수 구하기
        #print("num of: ", num_of_coins)
        K %= coin #남은 돈 구하기
        #print("k:", K)

print(num_of_coins)