📖문제

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

입력 조건

• 첫째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10000)
• 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

출력 조건

• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.
• 불가능할 때는 -1을 출력한다.

📝풀이과정

• dp[i]를 i원을 만들기 위한 최소한의 화폐 개수로 두었다.
• 화폐 단위를 k라고 했을 때 i원을 만드는 방법은 (i - k)원에다가 k원을 더하는 것이다.
• 따라서 dp[i]는 각각의 화폐 단위 k에 대해 (dp[i - k] + 1)들의 최솟값이다.

⌨코드

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())

# DP 테이블을 -1로 초기화
dp = [-1] * 10001

money = []
for i in range(n):
  money.append(int(sys.stdin.readline().rstrip()))
  # 화폐 단위만큼의 금액은 화폐 1개로 만들 수 있다.
  dp[money[i]] = 1

for i in range(1, m + 1):
  # 각각의 화폐 단위 j
  for j in money:
    # DP 테이블의 범위를 넘어가지 않도록 걸어둔 조건문
    if i - j > 0:
      # 금액 (i - j)를 만드는 방법이 존재한다면
      if dp[i - j] != -1:
        # dp[i]값 갱신
        if dp[i] == -1:
          dp[i] = dp[i - j] + 1
        else:
          dp[i] = min(dp[i], dp[i - j] + 1)

print(dp[m])