[그리디] 백준 11047번 동전 0 Python 풀이

문제 요약

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하라.

 

백준 11047번 문제 바로가기

입력

첫째 줄에 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

입출력 예시

입력	출력
10 4200 1 5 10 50 100 500 1000 5000 10000 50000	6
10 4790 1 5 10 50 100 500 1000 5000 10000 50000	12

코드

N, K = map(int, input().split())
coin_kind = []
total_coin = 0

for _ in range(N):
    coin_kind.append(int(input()))
coin_kind.sort(reverse=True)
for i in coin_kind:
    if i <= K:
        coin = K // i
        K -= (K // i) * i
        total_coin += coin
print(total_coin)

피드백

큰 수부터 계산을 해야해서 큰 수부터 저장되어 있도록 정렬

(오름차순으로 입력한 대로 계산하려니 좀 귀찮아서...)

문제도 간단하고 해결법도 간단해서 어렵지 않게 풀었다.

다른 사람 풀이 참고

python 풀이 중 1위에 있던 코드

N, K = map(int, input().split())

Coins = []
for i in range(N) : Coins.append(int(input()))


ans = 0
while K > 0 :
    coin = Coins.pop()
    ans += K // coin
    K %= coin

print(ans)

입력을 위한 반복문을 한줄로 붙여 작성할 수 있음

내가 반대로 sort하여 계산한 것을 .pop()으로 바로 꺼내어 계산했다. C언어의 스택에서 pop이 사용되는 것을 알고 있었는데 python의 list에서도 사용할 수 있는 건 몰랐다. 더 편하게 사용할 수 있을 것 같다.