[동적계획법/DP] 백준 2294 동전 2 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2294번: 동전 2

 

 

 

2. 문제 풀이

 동전의 개수가 최소가 되도록 만들어야 합니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 대표적인 DP문제 중 하나로, 일명 동전 거스름돈 문제입니다. 동전의 액수가 각각의 배수가 아니므로, 그리디 알고리즘으로 풀 수가 없습니다. (현재 선택이 이후의 선택에 영향을 줌)

 따라서, 일일이 동전을 넣고 빼보면서 최소의 동전 개수를 계산해야 합니다.

 

# c원 동전을 넣었을 때, 동전 개수가 더 적다면 갱신
cache[cost] = min(cache[cost], cache[cost-c]+1)

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n, k = map(int, input().split())
coin = set()  # 가치가 같은 동전 배제
for _ in range(n):
    coin.add(int(input()))

# DP
cache = [10001]*(k+1)
for cost in range(k+1):
    for c in coin:
        if cost == c:
            cache[cost] = 1
        elif cost-c >= 0:
            cache[cost] = min(cache[cost], cache[cost-c]+1)

# 출력
if cache[k] == 10001:
    print(-1)
else:
    print(cache[k])

 DP 테이블을 만들기 위해, 0원부터 k원까지 1씩 늘리면서 동전의 개수를 계산합니다.

 동전의 가치와 동일하면, 그 동전 1개로 거슬러줄 수 있습니다.

 동전의 가치보다 남은 돈이 많다면, 해당 동전을 추가했을 때 동전의 개수가 줄어들면 추가합니다.