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

문제

• 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

3 4
3
5
7

출력 예시

5

-1

풀이

• DP 테이블은 금액 i 를 만들 수 있는 최소한의 화폐 개수를 의미합니다.
• 따라서, 주어진 화폐의 단위를 k 라고 했을 때, 아래와 같은 점화식을 사용할 수 있습니다.
  • 금액 i 를 만들기 위해 마지막으로 사용한 화폐가 k 라면,
  • DP(i-k) 를 만드는 방법이 존재할 경우 : DP(i) = min( DP(i), DP(i-k)+1 )
  • DP(i-k) 를 만드는 방법이 존재하지 않을 경우 : DP(i) = 10,001
    • 10,001 은 특정 금액을 만들 수 있는 화폐 조합이 없다는 의미입니다.
    • 10,001 보다 더 큰 값을 사용해도 상관 없습니다.
• 따라서, 해당 점화식을 사용해, 각 화폐를 마지막으로 사용했을 때 가능한 조합이 있는지 반복문을 돌며 DP 테이블을 업데이트해 나갑니다.

예제 코드

import sys

# 정수 N, M을 입력 받기
n, m = map(int, sys.stdin.readline().rstrip().split())

# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(sys.stdin.readline().rstrip()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

참고

• 이것이 취업을 위한 코딩 테스트다. with python