효율적인 화폐 구성

이 문제는 이것이 코딩테스트다.226문제이다.

거스름돈 문제와 비슷하지만, 거스름돈은 최소단위의 돈이 있기에 그리디를 사용할 수 있다.

예를 들면 6원을 받았을때 거스름돈 문제는 1원단위의 돈이 있기때문에 어떤경우에도 거스름돈을 줄 수 있다.

하지만 이 문제에서는 1원단위의 돈이없을 수 있다. 그렇기에 다이나믹프로그래밍을 이용하여 풀어야 한다.

 

아래는 나의 코드이다.

import sys
moneyNum, moneyVal=map(int,sys.stdin.readline().split())
money=[]
for i in range(moneyNum):
    money.append(int(sys.stdin.readline().rstrip()))

money.sort()
dp=[-1]*10001

# 초기값 설정 동전화폐와 값이 일치하는 곳은 1로 처리
for i in money:
    dp[i] = 1

#dp 실행
for i in range(money[0],moneyVal+1):
    temp=[]
    if dp[i]==1:
        continue
    for j in money:
        #인덱스를 벗어나는 것을 방지
        if i<j:
            continue
        #dp[i-j]가 -1 이면 해당 단위 돈으로는 moneyVal을 만들수 없음을 의미, 다음 단위로 넘어감
        if dp[i-j]==-1:
            continue
        temp.append(dp[i-j])

    if len(temp)==0:
        continue
    else:
        dp[i]=min(temp)+1

print(dp[moneyVal])

아래는 예시코드

# 정수 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])