코딩 연습/Python

그리디 알고리즘 11047번

썬2 2021. 2. 5. 15:25

출처: www.acmicpc.net/problem/11047

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

import sys

N, K = map(int, sys.stdin.readline().split())

coins = list(sys.stdin.readline().strip() for _ in range(N))
coins = list(map(int, coins))

cnt = 0
for i in range(len(coins), 0, -1):
    if(K//coins[i-1] !=0):
        cnt = cnt + K//coins[i-1]
        K = K % coins[i-1]
    else:
        pass
print(cnt)

포인트: 입력받은 금액을 가장 큰 금액의 동전으로 나누다보면 최소한의 동전개수가 나온다.