[이코테][Python][DP] 효율적인 화폐 구성

 

import sys

put = sys.stdin.readline()

n, m = map(int, put.split())

arr = [0] * n
for i in range(n):
  arr[i] = int(input())

arr.sort(reverse=True)

cnt = 0
remain = m
for i in range(n):
  if arr[i] <= remain:
    cnt += remain // arr[i]
    remain %= arr[i]

if (remain == 0):
  print(cnt)

else:
  print(-1)

 

위의 방식은 그리드 방식이 가미된 방식이고

import sys

put = sys.stdin.readline()

n, m = map(int, put.split())

arr = [0] * n
for i in range(n):
  arr[i] = int(input())
arr.sort(reverse=True)

dp = [10001] * (m + 1)

dp[0] = 0
for i in range(n):
  for j in range(arr[i], m + 1):
    if (dp[j - arr[i]] != 10001):
      dp[j] = min(dp[j], dp[j - arr[i]] + 1)

if (dp[m] == 10001):
  print(-1)

else:
  print(dp[m])

위의 방식은 dp방식으로 구현한 것이다.

 

dp[j-arr[i]]가 존재할 때 dp[j] = min(dp[j], dp[j-arr[i]] +1) 라는 점화식을 구하면 그리디보다 쉽게 풀 수 있다.