다이나믹 프로그래밍 - 효율적인 화폐 구성

< 효율적인 화폐 구성 > 

[문제]

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

[입력]

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

[출력]

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

예제 입력	예제 출력
2 15 2 3	5
3 4 3 5 7	-1

---

아이디어

dp에 저장되는 것은 i원을 만들 수 있는 가장 적은 화폐 개수이다. dp[i]에 저장되는 것은 dp[i]와 dp[i - 화폐] + 1 중 작은 값을 저장한다. 하지만 dp[i - 화폐]가 0일 때는 불가능하기 때문에 처음에 dp의 모든 값을 경우의 수의 최댓값인 m보다 1 큰 m + 1로 초기화해준다.

풀이 및 코드

n, m = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))
# dp[i] : i번째 왔을 때 가장 적은 화폐 갯수
# dp는 나올 수 있는 최댓값인 m으로 초기화해줌
dp = [m + 1] * 10001
for coin in coins:
    dp[coin] = 1
for i in range(1, m + 1):
    for coin in coins:
        # 인덱스 에러 방지
        if (i - coin >= 1):
            # dp[i]와 dp[i - coin] + 1 중 작은 값 넣음
            dp[i] = min(dp[i], dp[i - coin] + 1)
# dp[m]이 만약 m + 1이라면 동전들 구성으로 만들 수 없다는 의미
print(dp[m] if (dp[m] != m + 1) else -1)

후기

dp를 0이 아닌 다른 값으로 초기화시켜줄 수도 있다는 것을 알 수 있는 문제였다.