Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 11047 동전 0
백준 11047 동전 0
문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다.
이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
- 첫 번째 줄: n, k
- 두 번째 줄 ~: 동전의 가치
출력
K원을 만드는데 필요한 동전 개수의 최솟값
해결 방식
greedy 알고리즘
- 입력받은 동전의 가치를 내림차 순으로 정렬
- 가장 큰 금액의 동전으로 k를 구성함
예시
k = 4200
coins = [1, 5, 100, 1000, 5000]
- 역순으로 정렬
- coins = [5000, 1000, 100, 5, 1]
- 5000원으로 구성?
- k // 5000 = 0
- k % 5000 = 4200
- 0개, 남은 돈 4200원
- 1000원으로 구성?
- k // 1000 = 4
- k % 5000 = 200
- 4개, 남은 돈 200원
- 이와 같은 과정 반복
- 결과: 6
코드
n, k = map(int, input().split())
coins = list(int(input()) for _ in range(n))
coins.sort(reverse=True)
result = 0
for coin in coins:
result += k // coin
k = k % coin
print(result)
