[다이나믹 프로그래밍 알고리즘] 효율적인 화폐 구성 - 파이썬(python)

효율적인 화폐 구성

난이도 : 中 풀이 시간 : 30분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

n, m = map(int, input().split())

coins = []
for i in range(n):
    coins.append(int(input()))

dp_table = [10001] * (m + 1)

dp_table[0] = 0

for i in range(n):
    for j in range(coins[i], m+1):
        if dp_table[j - coins[i]] != 10001:
            dp_table[j] = min(dp_table[j], dp_table[j - coins[i]] + 1)

if dp_table[m] == 10001:
    print(-1)
else:
    print(dp_table[m])

---

예시

 

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

---

해설

 

n, m, array에 입력을 받습니다. 그리고 dp 테이블을 생성해줍니다.
d[0] 시작값을 0으로 선언하고 for 반복문을 돌려 점화식을 사용합니다.
coins에 각 화폐 단위들이 저장되어 있으므로, j를 m+1까지 반복하여 (j-coins)를 만드는 방법이 있다면 dp 테이블의 [j - array[i]] 값에 횟수 1을 더해줍니다. 이를 반복하여 답을 도출해낼 수 있습니다.
마지막 출력할 때는 dp 테이블의 인덱스가 m인 경우가 10001 (방법이 없을 때) -1을 출력하고, 10001이 아니라면 (방법이 있을 때) dp 테이블의 m 값을 출력하도록 만들었습니다.