백준 11047번 그리디 알고리즘

링크

문제 설명

N종류의 동전으로 K를 만들라고 합니다.

근데 K를 만들 때 필요한 동전의 개수의 최솟값을 구하라고 하죠

K = 5500원

N = 10 50 500 1000

이라고 한다면 1000원 5개로 오천 원을 만들고

500원 한 개로 5500원을 만들 수 있죠

여기서 쓴 동전의 개수는 6개

이런 식으로 구하라는 거예요

case , money = map(int , input().split(' ')) #case는 동전의 종류 money는 우리가 만들어야할 돈
coin = [] #동전들을 담을 배열
temp = count = 0

for i in range(case):
    user_coin = int(input())
    coin.append(user_coin)

for m in reversed(coin): #입력은 오름차순으로 입력된다했죠 근데 최소값을 구하라고하니까 뒤집어서 큰 동전부터 검사합니다
    temp = money//m  #만약에 돈이 5300원이고 동전이 2000원이면 2번 뽑아줄수있죠
    count += temp #동전으로 돈을 나눈 몫을 count에 담아줍니다
    money %= m #돈을 뽑을수있는대로 뽑아줬으면 돈을 동전으로 나눈 나머지로 치환해줍니다

print(count)