[백준] 11047 - 동전 0 (Python)

문제 출처:

www.acmicpc.net/problem/11047

11047번: 동전 0

문제 풀이:

• 이 문제가 DP가 아니고 Greedy 문제라는 것을 알 수 있는게 문제에서 보면 주어지는 코인이 서로 배수 관계를 가지고 있으며 정렬되어 주어진다는걸 알 수 있다.
• 사실 배수관계만 유지되면 정렬은 우리가 해주어도 된다. 배수관계가 중요한 포인트인 이유는 배수관계를 유지함으로써 local optimal solution을 구하더라도 global로 optimal 하다고 생각할 수 있기 때문이다.( 앞 단계에서 A코인 2개를 쓴다고 해도 결국 이건 그보다 큰 B코인 1개로 치환이 가능하다. 배수관계로 주어지니까)
• 때문에 매 순간마다 값이 허락하는 한에서 최대로 코인을 고르도록 코딩해주면된다.

n,k = map(int,input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))

cnt=0
for i in range(n-1,-1,-1):
    cnt += k//coins[i]
    k = k%coins[i]
    #print(1,cnt)
    #print(2,k)

print(cnt)