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

11047번: 동전 0

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전의 수를 최소로 하려면 당연히 가치가 큰 동전들을 최대한 많이 써야할 것이다.

금액은 이미 오름차순으로 주어졌으므로 따로 정렬할 필요없이 역순으로 살펴보면 된다.

가장 큰 동전부터 쓸 수 있는 최대 개수로 사용하도록 한다. 사용할 수 있는 최대 개수는 남은 금액을 현재 코인의 가치로 나눈 몫이다. 그리고 남은 액수는 현재 코인으로 채운 금액을 제외한 값이므로 원래 금액을 현재 코인의 가치로 나눈 나머지값이 된다.