BOJ : 11047 동전 0

coin_values : 가지고 있는 동전의 가치들의 배열. reverse 를 이용하여 내림차순으로 정렬한다

getMaxCoin(sum, start) : start 이후의 index 를 가지는 coin_value 들 중 sum 보다 작거나 같은 최대 가치 (낼 수 있는 최대 가치의 화폐) 를 return 한다.
start는 직전에 낸 화폐의 Index를 저장하여 중복 체크를 막기 위함이다.

import sys

# index >= start  코인들 중 sum 보다 작거나 같은 최대 가치와 그 때의 index를 반환한다.
def getMaxCoin(sum, start):
    for i in range(start, len(coin_values)):
        if sum >= coin_values[i]:
            return coin_values[i], i

type_num, result_sum = list(map(int, sys.stdin.readline().strip().split()))

coin_values = [int(sys.stdin.readline().strip()) for _ in range(type_num)]
coin_values.reverse()

coin_count = 0
maxIndex = 0
while result_sum != 0:
    maxValue, maxIndex = getMaxCoin(result_sum, maxIndex)
    coin_count += result_sum // maxValue
    result_sum = result_sum % maxValue


print(coin_count)