문제
접근
그리디 알고리즘으로 해결할 수 있다.
그리디 알고리즘은 특정 조건으로 선택했을 때 결과가 항상 가장 좋음을 보장할 수 있을 때 사용할 수 있다.
이 문제의 경우 동전들이 항상 이전 동전의 배수이며, 첫 동전은 1이다.
이는 가능한 가장 가치가 큰 동전을 사용했을 때 항상 최상의 결과를 보장해준다.
예를 들어 5000원을 만들 때, 5000원 한장을 쓰는 것이 1000원 5장을 쓰는 것보다 좋다.
이는 화폐의 단위가 배수를 만족하기에 가능하다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
n, k = map(int, input().split())
arr = [int(input()) for _ in range(n)]
ans = 0
idx = 1
while k > 0:
ans += (k // arr[-idx])
k %= arr[-idx]
idx += 1
print(ans)