[백준 파이썬] 11047 동전 0

📌문제 출처

백준 단계별 문제풀이 - 그리디 알고리즘
https://www.acmicpc.net/problem/11047

11047번: 동전 0

❓ 문제

 

 

❗ 풀이

- 제일 가치가 큰 동전부터 최대로 채우기

📗 풀이 코드

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
coins = []
for _ in range(n):
    coin = int(input())
    if coin <= k :
        coins.append(coin)
    else :
        continue # k원보다 큰 코인은 coins 배열에 넣지 않는다.
coins = sorted(coins,reverse=True) # coins 내림차순 정렬
ans = 0
for coin in coins: # 제일 큰 코인부터 꺼내면서 
    cnt,k = divmod(k,coin) # cnt는 몫으로 코인 개수 / k는 나머지로 초기화
    ans += cnt # ans에 코인 개수 추가
    if not k : # 필요 금액을 다 채웠다면
        print(ans)
        break

📗 코드 해설

• 필요 금액보다 큰 동전은 사용하지 않기 때문에 저장하지 않는다.
• 동전의 가치는 배수로 커지기에 가치가 큰 동전을 최대로 사용하고 그 다음 동전을 사용할 것이다.
• divmod를 사용하여 몫과 나머지로 동전의 개수와 남은 가치를 초기화