백준 / 11047번 / 동전 0 / Greedy Algorithm / python 파이썬

 

문제 : https://www.acmicpc.net/problem/11047

 

 

코드 

import sys
input = sys.stdin.readline
n, k = map(int, input().split())

coin = []
for i in range(n):
    coin.append(int(input()))

count = 0
for i in reversed(range(n)):
    count += k // coin[i]
    k %= coin[i]
print(count)

 

큰 동전이 작은 동전의 배수가 된다는 조건이 있으므로, 그리디 알고리즘을 사용하여 풀 수 있다.

count에 가장 큰 동전으로 나눈 몫을 더해주고, 그 나머지를 k로 두며 반복하면 동전 수의 최솟값을 구할 수 있다.