문제 설명
준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
예제 입력
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
예제 출력
6
문제 풀이
동전을 액수별로 내림차순 정렬한 뒤, 앞에서부터 나누었을때 몫이 0이상인경우(나눠지는 경우)에 대해 가능한만큼의 금액을 price에서 빼고, 사용한 동전의 개수를 누적개수에 더한다.
이 문제는 큰 동전의 단위가 항상 작은 동전의 단위의 배수이기 때문에 최적해를 구할 수 있다. 그러나 큰 동전의 단위가 작은 동전의 단위의 배수가 아닐 경우 최적해를 구하지 못한다. 따라서 그리디 알고리즘은 최적해를 보장해주지 않는다. 다만, 계산 속도가 매우 빠르다는 장점이 있다.
ex)
10, 30, 70, 100 단위의 동전이 있을때 140 원을 최소 동전의 개수를 사용할때 그리디 알고리즘으로는 100원 1개, 30원 1개, 10원 1개 를 사용하여 총 3개의 동전을 사용한다. 그러나 최적해는 70원 2개를 사용하는 것이다. 이러한 최적해는 다이나믹 프로그래밍으로 구할 수 있다.
n, price = map(int, input().split())
arr = []
sum = 0
for i in range(0,n):
arr.insert(0, int(input()))
for m in arr:
if price // m != 0:
sum = sum + price // m
price = price - m*(price//m)
print(sum)