[DP] 효율적인 화폐구성

1. 문제 설명

몇 개의 화폐와 TargetNumber 주어진다. 해당 화폐를 가지고 주어진 수를 만들기 위한 최소한의 경우를 구하라. 

- df에 만들 수 있는 최소의 경우의 수를 찾는다. 덧셈으로 값이 구성이 된다.따라서 들어오는 array마다 조건이 달라질 것이다.

- 값이 증가하지 않는다면 -1을 넣어야 하지만 최소의 경우의 수를 구해야 하기 때문에 큰 금액을 넣어준다.

2. 코드

# 입력
n, m = list(map(int, input().split()))
array = []
for i in range(n):
    array.append(int(input()))
money = list(set(array))
"""
2 15
2
3
"""

# DP
df = [10001]*(m+1)
df[0] = 0

# 값을 찾을 때까지 for문을 돈다.
for token in money:
    for i in range(token, m+1):
        if df[i-token] !=10001:
            df[i] = min(df[i], df[i-token]+1)
if df[m] ==10001:
    print(-1)
else:
    print(df[m])

# >> 5

3. 코멘트

- DP 문제의 경우 코드는 간결하지만, 알고리즘을 구현하기 위한 점화식을 생각하기까지 시간이 걸리는 것 같다.

- 특히, 이번 문제의 경우 `i-token`을 하는 과정에서 꽤나 시간을 썼던 것 같다.