[Python]그리디 알고리즘 백준 11047

 문제

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

그리디 알고리즘이 무엇인지 알려주기 위해 만든 문제인거같다.

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그리디 알고리즘이란 탐욕 알고리즘 이다.

매순간 최적이라고 생각되는것을 선택해 나가는 방식으로 진행하여 해답을 도출한다.

합보다 작은 동전 중 가장 큰 동전부터 최대한 넣어주고 다음 동전으로 넘어가는 식으로 

짜면될거같다.

N,K=map(int,input().split())
 
coin_list=[int(input()) for _ in range(N)]
count=0
for i in range(N-1,-1,-1):
    if coin_list[i]<K:#가치의 합보다 코인이 작다면
        count+=K//coin_list[i]
        K=K%coin_list[i]
    elif coin_list[i]==K:
        count+=1
        break
    else:
        continue
 
print(count)