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

풀이

arr은 오름차순으로 나열되었으므로 뒤에 있는 수에서 반복문을 시작한다.
해당 원소가 k보다 작거나 같다면, 이 동전을 사용할 수 있다.
k원을 해당 원소로 나눈 몫을 구한다. 그것이 동전 개수가 되기에 cnt에 더한다.
k에서 동전 개수와 해당 원소(가격)를 곱한 값을 뺀다.

k가 0이 되면 더이상 계산할 필요가 없으므로 반복문을 중지한다.

소스코드

import sys
input = sys.stdin.readline

n, k = map(int, input().strip().split())
arr = [int(input()) for _ in range(n)]
cnt = 0

for i in range(1, n+1):
    if arr[n-i] <= k:
        cnt += k // arr[n-i]
        k -= arr[n-i] * (k // arr[n-i])

    if k == 0:
        break

print(cnt)