[백준 11047 파이썬 ] Greedy Algorithm 1 - 동전 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

풀이 전략	현재 값 K보다 작거나 같으면서 가장 큰 수 A를 찾습니다. K 값을 A로 나눠준 몫 Q를 구합니다.  K 값에서 A*Q 값을 빼줍니다.  동전을 사용한 게 Q개 증가합니다.
주의사항	작거나 같은 동전이 없을 수 있으므로 A 값을 맨 마지막 값으로 초기화 합니다.

# 동전 0
# Greedy Algorithm
 
n, target = map(int, input().split())
values = [0 for i in range(n)]
for i in range(n):
    values[i] = int(input())
 
# 최대 value를 찾아서 필요한 개수만큼 빼준다. 
count = 0
while target>0:
    closest = values[-1]
    for i in range(n):
        if target-values[i]<0:
            closest = values[i-1]
            break
    temp = target//closest
    count += temp
    target -= temp*closest
 
print(count)