[백준 11047] 동전 0

문제

https://www.acmicpc.net/problem/11047

11047번: 동전 0

---

아이디어

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

- 위의 조건 때문에 Ai번째 동전의 액수는 Ai-1번째 동전으로 만들 수 있게 된다. 즉 모든 상황에서 가장 비싼 금액의 동전을 사용하는 것이 가장  최적의 선택이 된다. 

- 따라서, 이 문제는 그리디 알고리즘으로 접근할 수 있게 된다.

 

그리디 알고리즘은 다음과 같이 구현했다. 

- n : 동전의 개수

- t : 총 가치

- lst : 동전들의 list 

 

1. 가장 비싼 금액의 동전을 꺼낸다.

- 1.1. 만약, 이 동전의 가치가 총 가치보다 크다면 이 동전으로는 k의 가치를 만들 수 없게 된다. 

- 1.2. 이 동전의 가치가 총 가치보다 작다면, 이 동전을 가능한 한 많이 사용해서 k에 가깝게 만든다.

• ex. 총 가치가 4200원일 때, 500원짜리 동전을 꺼냈다면 500원짜리 동전 8개를 이용해서 4200원을 만든다.
• divmod(4200, 1000)을 사용하면 사용한 동전 개수 4, 남은 금액 200이 반환된다. 
• 위의 과정이 끝나면 k값은 4200 -> 200이 된다.

2. 그 다음으로 낮은 가치를 가진 동전을 꺼내서 1의 과정을 반복한다. 

3. 만약 k가 0이 되면 모든 동전으로 k만큼의 가치를 만들었다는 뜻이기 때문에 모든 과정을 종료하고 answer를 반환한다.

---

Solution

n, k = map(int, input().split())
answer = 0
lst = [int(input()) for i in range(n)]

while True :
    m = lst.pop()
    if k >= m : 
        times, k = divmod(k, m)
        answer += times
    if k == 0 : 
        break
    
print(answer)