[이코테 다이나믹 프로그래밍] 효율적인 화폐 구성

# 문제

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

# 입력 

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

 

# 출력

• 첫째 줄에 경우의 수 X를 출력한다.
• 불가능할 때는 -1을 출력한다.

# 입력 예시

# 입력 예시 1
2 15
2
3
# 입력 예시 2
3 4
3
5
7

# 출력 예시

# 출력 예시 1
5
# 출력 예시 2
-1

 

---

내 풀이

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

dp = [0] * (m + 1)

for i in range(1, m + 1):
    # 보유한 화폐 하나로 구성할 수 있는 금액인 경우
    if i in value:
        dp[i] = 1
        continue

    for v in value:
        # (i - v) 금액의 화폐 구성이 가능하고 아직 i 금액의 화폐 구성을 안해본 경우
        if dp[i - v] != 0 and dp[i] == 0:
            dp[i] = dp[i - v] + 1
        # (i - v) 금액의 화폐 구성이 가능하고 이미 i 금액의 화폐 구성 시도가 있었던 경우
        if dp[i - v] != 0 and dp[i] != 0:
            dp[i] = min(dp[i], dp[i - v] + 1)  # 최소 화폐 개수 체크

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