백준 알고리즘 - 11047. 동전 0

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

11047번: 동전 0

 

전체 코드

def solution(amount, coins):
    if len(coins) == 0:
        return 0

    count = 0
    coin = coins.pop()
    while amount > 0:
        if amount < coin:
            if not coins:
                break
            coin = coins.pop()
        else:
            add_count, amount = divmod(amount, coin)
            count += add_count
            # --- 시간 초과 ----
            # amount -= coin
            # count += 1

    return count

# --- submit ----
start_line = input()
line_count, amount = map(int, start_line.split(' '))
coins = [int(input()) for _ in range(line_count)]

print(solution(amount, coins))

 

여담

동전 반환 개수 계산을 한번씩 계산하면 time-out이 발생한다. divmod를 통해 몫, 나머지를 한번에 계산하여 최적화를 하여 pass 하였다.