Python으로 푸는 백준 11047.동전 0

백준 11047.동전 0 

문제에서는 준규가 가지고 있는 동전의 종류만 가지고 K 금액을 만들려고 할때,

이때 필요한 동전 개수의 최솟값을 구하려고 한다. 

문제 보러 가기

github에서 코드 보기

문제에서 제시한 조건

1. N개의 줄에 동전의 가치가 오름차순으로 주어진다. 두번째 줄부터 입력되는 동전의 가치는 앞의 동전의 배수이다.

문제 풀이 방법

- 입력 조건 중에 동전의 가치는 오름차순으로 주어지며, 동전의 가치는 앞 동전의 가치의 배수라는 조건이 있기 때문에 그리디 알고리즘으로 문제를 풀 수가 있다. 

- 동전의 종류를 입력 받을 때 K원을 초과하는 종류가 나온다면 어차피 사용하지 않을 동전의 가치이므로 입력을 중단하고 코인의 수를 계산하는 코드로 넘어가자.

- 동전의 종류를 내림차순으로 정렬하자. K금액을 지불할 때 동전의 수를 줄이려면 큰 단위의 동전을 많이 사용하는게 좋다.

- 정렬한 coin으로 K 금액을 최대한 지불하고 남은 금액을 남은 동전의 가치로 나누어가자.

- K 금액이 0 원이 되었을 때 코드를 종료하고 동전의 갯수를 반환한다.

파이썬 코드

import sys
 
def greedy(bank, k):
    count = 0
    bank = list(reversed(bank))
    total = k
 
    for coin in bank:
        if total % coin >= 0 and total >= coin:
            cnt = total // coin
            count += cnt
            total -= cnt * coin
        if total == 0:
            break
    return count
 
 
if __name__ == "__main__":
    n, k = list(map(int, sys.stdin.readline().strip().split()))
    bank = []
    for i in range(n):
        coin = int(sys.stdin.readline().strip())
        if coin > k:
            break
        bank.append(coin)
    print(greedy(bank, k))

#Python Greedy 11047 #백준 11047 #python 백준 11047 #백준 11047 python #백준 11047.동전 0 #11047.동전 0 #백준 11047 동전 0 #백준 동전 0 #백준 동전 0 python #python 백준 동전 0 #파이썬 백준 동전 0 #백준 동전 문제 #백준 동전 0 문제 #백준 그리디 알고리즘 문제 #백준 11047 python #python 백준 11047