[Python] BOJ(백준) 11047번 - 동전 0

1. 링크

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

2. 난이도(solved.ac 참고)

실버2

3. 풀이

	import sys
	n, k = list(map(int, sys.stdin.readline().split()))
	coin_list = []
	for _ in range(n):
	coin_list.append(int(sys.stdin.readline()))
	coin_list.sort(reverse=True)
	count = 0
	for i in coin_list:
	count += k // i
	k %= i
	print(count)

view raw 동전0.py hosted with ❤ by GitHub

그리디의 대표 문제이다. k에서 i를 나눈 몫을 count에 더해주고, k를 i로 나눈 나머지를 k에 지정한다.

위 예제 입출력을 예시로 들어서 설명해보겠다. 현재 k는 4200원이고, 리스트에는 1원부터 5만원까지의 금액이 있다.

4200원은 5천원~5만원으로 나눴을 때는 몫이 0이다. 천원으로 나눴을 때 비로소 몫이 발생한다. 그래서, i가 1000일 때 k를 i로 나눈 몫을 count로 지정을 해 주는 것이다.

 

이렇게 되면 count는 천원짜리 네 개가 추가되어 4가 되고, k는 4200 % 1000 = 200원이 된다. 이와 같은 계산을 반복하는 것이다.

4200 -> 200 -> 0. 남은 돈이 0이 되면 끝이므로, 최종적으로 4200원은 1000원짜리 동전 4개와 100원짜리 동전 2개로 했을 때 최소 개수가 되는 것이다.