[BaekJoon] 백준 11047번 : 동전 0

11047번 : 동전 0

이 문제는 그리디 알고리즘을 사용하면 풀 수 있다.

주어진 각각의 동전 중 가장 액수가 큰 동전부터 나누기를 통해 몫을 필요한 동전 개수에 더하고 나머지를 다시 계산하면 된다.

4790 % 50000 = 4790 (0, 4790)

4790 % 10000 = 4790 (0, 4790)

4790 % 5000 = 4790 (0, 4790)

4790 % 1000 = 790 (4, 790)

4790 % 500 = 290 (1, 290)

4790 % 100 = 90 (2, 90)

4790 % 50 = 40 (1, 40)

4790 % 10 = 0 (4, 0)

---

def make_min_coin(coin, k):
	coin_cnt = 0

	for val in reversed(coin):
		coin_cnt += k // val
		k %= val

		if k == 0:
			break
	print(coin_cnt)


in_n, in_k = map(int, input().rsplit())
in_coin = []

for _ in range(in_n):
	in_coin.append(int(input()))

make_min_coin(in_coin, in_k)