문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

동전 문제라고 해서 여러 가격의 구매 가능한 모든 조합을 찾는 프로그램을 떠올렸습니다.

그 알고리즘에서는 빠르게 모든 0으로 떨어지는 조합을 찾기 위해 비싼 물건을 앞에 두고 싼 물건을 나눗셈 계산해 계산 횟수를 줄이지만, 여기서는 최소 개수의 화폐로 0을 만들면 됩니다.

그래서 가장 비싼 화폐를 뒤에 두고 나눗셈으로 계산해 첫 사례가 나오면 출력하고 탈출하면 된다고 생각해서 그리디를 변형해 보았습니다.

import sys
values_length, target = map(int,input().split())
values = list(map(int,sys.stdin.readlines()))
last_node = values_length - 2
last_index = values_length - 1
node = -2
quantities=[0 for i in range(values_length)]
balances=[0 for i in range(values_length)]
is_overrun = False

while not (node == -1 and is_overrun == True):
    # quantity[n]의 아이템 개수와 단가의 곱만큼 예산에서 빼고 잔액에 저장합니다.(마지막 아이템 제외)
    balances[-1] = target
    for n in range(last_index):
        balances[n] = balances[n - 1] - (quantities[n] * values[n])
    # 마지막 아이템을 몇 개 살 수 있는지 계산합니다.
    quantities[-1] = balances[-2] // values[-1]
    balances[-1] = balances[-2] - (quantities[-1] * values[-1])

    if any([i < 0 for i in balances]):
        is_overrun = True
        quantities[node] = 0
        node -= 1
    else:
        is_overrun = False
        node = last_node
        # IF Balance is $0, then save it to the case_exact
        if (balances[last_index] == 0):
            print(sum(quantities))
            break
    # PREPAIR NEXT CASE
    quantities[node] += 1

됩니다.

그런데 백준에서는

시간 초과가 뜹니다. 불필요한 리스트가 너무 많습니다.

그래서 그냥 코드 재활용 없이 풀기로 했습니다.

어차피 나누어 떨어진다는 확신이 있기 때문에