[백준/파이썬] 11047번 동전 0 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 11047번 동전 0
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

서로 다른 가치의 동전들이 주어질 때, 합이 K가 되도록 하는 최소 동전 개수를 구하는 문제입니다.

입력으로 주어지는 동전 체계에서는 큰 단위부터 greedy하게 선택해도 최적해가 보장됩니다.

코드

n, k = tuple(map(int, input().split()))
money = list()

for _ in range(n):
    money.append(int(input()))


money.sort(reverse=True)

cnt = 0
for m in money:
    if(m <= k):
       cnt += k//m
       k %= m
       
print(cnt)

설명

동전 가치를 내림차순으로 정렬한 뒤, 각 동전에 대해:

• 현재 금액 k에서 가능한 만큼 사용하고
• 남은 금액을 다음 동전으로 넘깁니다.

즉 cnt += k // coin, k %= coin를 반복하면 됩니다.

---

• 백준 문제풀이 전체 목록 보기

---