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

Problem

동전을 많이 가지고 있는 상태에서, 주어진 가격을 최소한의 동전의 개수로 채우는 문제

Solution

주어진 동전 리스트를 역순으로 정렬하여 값이 큰것부터 계산해주고 차액은 빼주기

코드설명

1)동전리스트입력->역순으로 정렬
2)동전리스트중 목표값을 배수형태로 곱할수 있으면 최대한 더하기
3) 2)과정의 값들을 목표값에서 빼주고 반복

Python Code

import sys

N,K=map(int,sys.stdin.readline().split())
coinList=[]
cnt=0

for _ in range(N):
    tmp=int(sys.stdin.readline())
    coinList.append(tmp)

coinList=sorted(coinList,reverse=True)

for i in range(0,len(coinList)):
    if K>=coinList[i]:
        cnt+=K//coinList[i]
        K-= coinList[i] * (K//coinList[i])

print(cnt)