풀이
학교 알고리즘 동아리에서 제공한 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)