효율적인 화폐 구성 - PYTHON

문제 설명

N가지 종류의 화폐 중에서 화폐의 개수를 최소한으로 이용해 그 가치의 합이 M원이 되도록 한다. 화폐 갯수는 무제한이며 순서가 달라도 같은 걸로 친다.
불가능시 -1을 출력한다.

예시

2,15
2
3

문제 풀이

처음에는 이진 탐색으로 진행하려 했지만, 완벽하게 m 이 나누어 떨어지지 않는 예외 때문에 화폐 개수의 최소~최대 범위를 추정하기 힘들다. 그래서 다른 알고리즘을 생각해 보며 원하는 값이 m원이 되는 최소 화폐 개수이고 이 m을 만들기 위해서는 m - 2 , m - 3원 각각을 만들기 위해서는 또 m - 2 - 2, m -2 - 3 , m - 3 - 2 , m - 3 -3.....이런 식으로 마치 피보나치 구조를 띄고 있다. dp[i] = i를 만들기 위한 최소한의 화폐 개수 라고 가정하고 화폐 단위를 x로 가정하면 dp[i] = min(dp[i] , dp[i - x] + 1) 지만 만약 i-x를 할 수 없는 경우는 INT_MAX로 무시할 수 있게 해준다.

n , m = map(int,input().split())
money = []
for i in range(n):
  money.append(int(input()))

dp = [100001] * (m+1)
dp[0] = 0

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

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