[이코테 실전문제] 효율적인 화폐 구성 - python

효율적인 화폐 구성

문제

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

입력조건

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

출력조건

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

풀이

N으로 만들기와 비슷한 문제

[2, 3] 일때 1원 만들기

x

2원 만들기

2

3원 만들기

3

4원 만들기

2 + 2

5원 만들기

3 + 2

6원 만들기

4 + 2 (o)
5 + 1 (x)
3 + 3 (o)

7원

7 = 6 + 1
  = 5 + 2
  = 4 + 3

1<=n <=m으로 (n - 1) + 1 부터 (n+1//2 +1) + n+1//2 까지 중에 최솟값을 찾으면 된다.

n, m = map(int, input().split()) # n가지 종류 화폐, M원 
arr = [int(input()) for _ in range(n)]
dp = [float('inf')] * (m + 1)
dp[0] = 0
​
for target in range(1, m + 1):
  mid = (target + 1) // 2
  if target in arr: # 만들려고하는 수가 화폐 단위인 경우
    dp[target] = 1
    continue
  for i in range(1, mid + 1): # 가능한 경우 중에 최소 값 저장
    dp[target] = min(dp[target], dp[i] + dp[target - i])
​
if dp[m] == float('inf'):
  print(-1)
else:
  print(dp[m])

근데 m이 너무 커서 느림

다른 방법

작은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾는다.

금액 i를 만들 수 있는 최소한의 화폐 개수를 a, 화폐 단위를 k라고 했을 때

A[i-k]를 만들 수 있는 경우 : A[i] = min(A[i], A[i - k] + 1)

A[i-k]를 만들 수 없는 경우: A[i] = INF

n, m = map(int, input().split()) # n가지 종류 화폐, M원 
arr = [int(input()) for _ in range(n)]
​
dp = [float('inf')] * (m + 1)
dp[0] = 0
​
for k in arr:
  for j in range(k, m + 1):
    dp[j] = min(dp[j], dp[j - k] +1)
​
​
if dp[m] == float('inf'):
  print(-1)
else:
  print(dp[m])