[이코테 Ch8-5] 효율적인 화폐 구성 (DP)

👩🏻‍💻문제설명

[이코테 Ch8-5] 효율적인 화폐 구성 (DP)

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

입력 조건

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

출력 조건

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

입력 예시 1

2 15
2
3

출력 예시 1

5

입력 예시 2

3 4
3
5
7

출력 예시 2

-1

✍️Idea Sketch

알고리즘 : 다이나믹 프로그래밍, Bottom-Up

시간복잡도

O(NM) : 이중반복문

이 문제는 작은 문제부터 차근차근 답을 도출하는 Bottom-Up 방식으로 구현했다. 가치 1원부터(작은 가치부터) 가치 M원까지 탐색하며, 한 번 탐색할 때마다 모든 화폐를 확인한다. 화폐 종류는 N개이므로 시간복잡도는 O(M*N)이 된다.

✍️내 소스코드

• dp 배열의 index는 가치, value는 화폐 개수이다. 처음에는 value를 무한대 값으로 초기화한다. 단 가치 0원을 만들기 위해 필요한 화폐 개수는 0개이므로 dp[0] = 0이다.
• 가치 1원부터 가치 M원까지 탐색하며, 한 번 탐색할 때마다 모든 화폐를 탐색한다. (이중반복문)
• 가치 m원을 만들기 위해 필요한 화폐 개수가 무한대인 경우 불가능하다는 뜻이므로 -1을 출력한다.

  import sys
  si = sys.stdin.readline

  n, m = map(int, si().split())
  coins = [int(si()) for _ in range(n)]

  dp = [float('inf')] * (m + 1)
  dp[0] = 0

  for i in range(1, m + 1):
    for coin in coins:
      if i >= coin:
        dp[i] = min(dp[i], dp[i - coin] + 1)

  if dp[m] == float('inf'):
    print(-1)
  else:
    print(dp[m])