Python 86 - 다이나믹 프로그래밍 실전문제4 ("효율적인 화폐 구성")

난이도 ●●○    l    풀이 시간 30분    l    시간 제한 1초    l    메모리 제한 128MB    l

문제 

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

입력조건

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

출력조건

• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.
• 불가능 할 때는 -1을 출력한다.

문제해설

이 문제는 그리디에서 다루었던 거스름돈 문제와 거의 동일하다. 단지 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점만 다르다. 그렇기 때문에 그리디 알고리즘을 사용했던 예시처럼 매번 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없고 다이나믹 프로그래밍을 이용해야 한다.

이번 문제는 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다. 

결과적으로 7원을 만들기 위한 최소의 화폐 개수는 2개이다. 따라서 앞서 언급한 점화식을 그대로 소스코드로 옮기면 다음과 같다. 또한 아래 코드에서 d[ j - array[ i ] ] 가 10001 인지 검사하는 부분은 사실 없어도 되는 코드인데

d[ j - array[ i ] ] 가 10001값을 가지더라도 min( d [ j ], d [ j - array [ i ] ] + 1) 은 항상 d [ j ] 값을 반환하기 때문이다.다만, 이해를 돕기 위해 코드에는 그대로 넣어주었다.

# 정수 N, M을 입력받기
n, m = map(int,input().split())
# n개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
                array.append(int(input()))
                
# 한 번 계산된 결과를 저장하기 위한 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 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding