BOJ 11047 - 동전 0

풀이

---

학교 알고리즘 동아리에서 제공한 2번째 그리디문제이다.

N 종류의 동전 중 최소한을 사용하여 K 를 만들어내면된다.

주어진 N 종류의 동전을 내림차순으로 정렬한 뒤 반복문을 통해 K//c 를 반복하면 정답이 나온다.

주의해야 할 점은 역시 N 종류의 동전이 배수로 이루어져있는지 확인해야한다.

문제에선 자기보다 큰 동전은 항상 배수라고 제한을 걸어두었으니 정상작동하는 것을 볼 수 있다.

소스코드

---

import sys
input = sys.stdin.readline
 
n, k = map(int, input().split())
coin = sorted([int(input()) for _ in range(n)], reverse=True)
ans = 0
 
for c in coin:
    ans += k//c
    k %= c
 
print(ans)

References

---

• BOJ 11047 - 동전 0