문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
코드
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
coin = []
for _ in range(n):
coin.append(int(input()))
ans = 0
for i in range(n-1, -1, -1):
ans += k // coin[i]
k = k % coin[i]
print(ans)
k원을 만드는데 필요한 동전의 수를 최소로 하려면 당연히 가치가 큰 동전들을 최대한 많이 써야할 것이다.
금액은 이미 오름차순으로 주어졌으므로 따로 정렬할 필요없이 역순으로 살펴보면 된다.
가장 큰 동전부터 쓸 수 있는 최대 개수로 사용하도록 한다. 사용할 수 있는 최대 개수는 남은 금액을 현재 코인의 가치로 나눈 몫이다. 그리고 남은 액수는 현재 코인으로 채운 금액을 제외한 값이므로 원래 금액을 현재 코인의 가치로 나눈 나머지값이 된다.
'문제풀이 > Greedy' 카테고리의 다른 글
[Python/파이썬] 백준 13305번 주유소 (0) | 2023.02.14 |
---|---|
[Python/파이썬] 백준 1541번 잃어버린 괄호 (0) | 2023.02.14 |
[Python/파이썬] 백준 11508번 2+1 세일 (0) | 2023.02.08 |
[Python/파이썬] 백준 11399번 ATM (0) | 2023.02.08 |
[Python/파이썬] 백준 1758번 알바생 강호 (0) | 2023.02.07 |