효율적인 화폐 구성

이것이 취업을 위한 코딩 테스트다. 8-8.py 답안예제로부터.

문제설명

1. 첫째 줄에 100보다 작은 자연수 N과 10000보다 작은 자연수 M이 주어진다.
2. 이후 각 줄로 N개의 화폐 가치가 나열된다.
3. M을 만들기 위한 최소한의 화폐 갯수를 출력하라.
4. 만들 수 없을 경우 -1을 출력하라

입출력 예제

    입력
    
    2 15
    2
    3

출력
  
  5
  

• 문제 풀다가 어떤 작은 정수 범위 내의 값을 상수 취급하여 절대적인 비교를 하도록 하는 게 맘에 안 들었음
• 파이썬에서 제공해주는 상수나 비교하면 항상 같은 결과를 가져오는 값이 있는지 확인해봄

	inf_num = float("inf")
    inf_num = float("-inf")

Code

import sys
from typing import Union

input = sys.stdin.readline

N, M = map(int, input().split())
coins = sorted([int(input()) for _ in range(N)])


def get_coin_num(coins: list[int], m: int) -> Union[int, float]:
    inf_num = float("inf")
    c = [inf_num] * (m + max(coins))
    c[0] = 0

    for i in coins:
        for j in range(i, m + 1):
            if c[j - i] != float("inf"):
                c[j] = min(c[j - i] + 1, c[j])

    return -1 if c[m] == inf_num else c[m]


print("필요한 최소한의 동전 갯수 : {}".format(get_coin_num(coins, M)))