[🥈2 / 백준 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

예제 입력 1 10 4200 1 5 10 50 100 500 1000 5000 10000 50000	예제 출력 1 6
예제 입력 2 10 4790 1 5 10 50 100 500 1000 5000 10000 50000	예제 출력 2 12

 

풀이

 

주어진 동전의 종류를 이용하여 가장 적은 동전의 개수로 입력된 금액을 만드는 문제이다.

 

가장 큰 동전의 종류부터 시작하여 내림차순으로 금액과 비교하며 개수를 늘려가면 된다.

 

import sys
input = sys.stdin.readline
n, k = map(int,input().split())
coin = [int(input()) for i in range(n)]
coinCount = [0] * len(coin)

for i in range(len(coin)-1,-1,-1):
    while(k >= coin[i]):
        k -= coin[i]
        coinCount[i] += 1
        
print(sum(coinCount))

 

하지만 예상치 못하게 시간초과에 걸리고 말았다.

 

이유가 무엇인가 알아보기 위해 coinCount 배열을 뒤적거려봤다.

 

n, k = 10, 987620800
coin = [1,5,10,50,100,500,1000,5000,10000,50000]

 

위와 같이 설정했을 때, coinCount는 다음과 같았다.

 

[0, 0, 0, 0, 3, 1, 0, 0, 2, 19752]

 

50000원 짜리 동전의 개수가 엄청나게 많아, while 함수가 저만큼 돌아가고 있다는 것이다.

 

 

k가 가장 큰 동전보다 크다면, 나눠서 몫을 더해버리도록 하자.

 

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
coin = [int(input()) for i in range(n)]
coinCount = [0] * len(coin)

if k >= coin[-1]:
    coinCount[-1] = k // coin[-1]
    k -= coin[-1] * coinCount[-1]

for i in range(len(coin)-2,-1,-1):
    while(k >= coin[i]):
        k -= coin[i]
        coinCount[i] += 1
        
print(sum(coinCount))