[백준(Baekjoon] 11047 동전 0

문제

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

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

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

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

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

예제 입력 1

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

예제 출력 1 

6

예제 입력 2 

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

예제 출력 2 

12

---

나의 코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
cnt = 0

for i in reversed(coins):
    if k == 0:
        break
    temp, k = divmod(k, i)
    cnt += temp

print(cnt)

 

---

풀이

 

[Algorithm] 그리디 (탐욕) 알고리즘

 

 

 

그리디 알고리즘이란?

 

매 선택에서 현재 상황에 지금 당장 좋은 것만을 선택하여 적합한 결과를 도출하는 알고리즘 설계 기법
이 방법은 선택하는 그 순간에는 최적인 방법이지만 최종적으로 보면 그 선택들이 최적이라는 보장은 없다. 
하지만 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많다. 

따라서 그리디를 이용하여 문제를 풀 때 이 문제가 그리디로 풀 수 있는지 확인하기 위해서는 반례를 찾는 것이 중요하다. 

---

동전 0 문제는 최소한의 동전 개수를 가지고 주어진 돈을 만드는 대표적인 그리디 문제이다. 

 

이 문제를 해결하는 방법은 가장 큰 화폐 단위부터 개수를 구해주면 된다. 

큰 단위가 항상 작은 단위의 배수이기 때문에 최적의 해가 나온다. 

 

ex) 380원을 100, 50, 10원으로 만들 수 있는 최소 동전 개수는?

380 // 100 = 3 -> 나머지 80

80 // 50 = 1 -> 나머지 30

30 // 10 = 3 -> 0

정답 7

 

100원 1개를 다른 단위로 대체하려면 50원은 2개, 10원은 10개가 되어야하기 때문에 100원을 사용하는 것이 최소가 된다. 

 

 

※ 주의 할 점 

화폐 단위가 배수가 아니라면 그리디 알고리즘으로 해결할 수 없다. 

 

ex) 160원을 100원, 80원, 30원으로 만들 수 있는 최소 동전 개수는?

위와 같이 그리디를 따른다면 

160 // 100 = 1 -> 나머지 60

60 // 80 = 0 -> 나머지 60

60 // 30 = 2 -> 나머지 0 

100원 1개, 80원 0개, 10원 2개로 총 3개를 사용해야 한다. 

 

하지만 80원 2개를 사용해야 가장 최소로 만들 수 있다. 

 

 

---

문제 출처

11047번: 동전 0