[백준/python] 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
N, K = map(int, sys.stdin.readline().split())
coin = []
answer = 0

for i in range(N):
    coin.append(int(sys.stdin.readline()))

for i in range(len(coin) - 1, -1, -1):
    if K == 0:
        break
    if K // coin[i] != 0:
        answer += K // coin[i]
        K = K % coin[i]

print(answer)

---

가장 가치가 큰 동전부터 가치의 합 K가 몇 개의 동전을 가질 수 있는지 확인한다.

 

가장 가치가 큰 동전부터 확인해야하므로 반복문의 범위를 coin의 마지막 인덱스부터 인덱스 0까지로 설정한다.

 

동전으로 나누었을 때 0이라는 것은 해당 동전보다 K가 작다는 뜻이므로 해당 동전으로 표현할 수 없다.

동전으로 나누었을 때 0이 아니면

최종 동전 개수 answer에 해당 동전이 몇개 쓰였는지 즉, K를 해당 동전으로 나눈 몫을 더해주고

K를 동전으로 나눈 나머지로 바꿔준다.

 

K가 0이라는 뜻은 K를 이전의 동전들로 모두 표현했음을 의미하므로 반복문을 나온다.