[Greedy Algorithm] BOJ11047: 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

​

예제 입력

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력

6

---

거스름돈 문제가 그리디 알고리즘을 이용한다는 것을 안다면, 풀 수 있는 문제이다 !

그리디 알고리즘은 순간 최적을 찾는 것으로 여기서의 최적은 '큰 돈'부터 나누는 것이다.

​

1. 첫째 줄에 사용할 수 있는 동전 개수 N과 우리가 구해야 할 돈인 K를 입력받는다.

2. 둘째 줄부터 우리가 사용할 수 있는 동전의 종류를 입력받고 reverse 한다.

왜? 큰 것부터 계산을 해야 되기 때문에

3. 반복문을 이용하여 큰 것부터 총액을 나눠주고 몫을 count에 누적해준다.

4. 또한 나머지를 구하여 반복하면 성공

​

다음부터는 주석을 달아 버릇 해보아야겠다. 이 설명을 나 혼자만 알아들을 것 같아 말이다

 

N, K = map(int, input().split())
A = []
for i in range(N):
  A.append(int(input()))
A.reverse()

count = 0
for i in A:
  count += K // i
  K %= i
print(count)

www.acmicpc.net/problem/5585

5585번: 거스름돈