[이코테] 효율적인 화폐 구성 문제 풀이 (파이썬)

문제 출처: https://youtu.be/5Lu34WIx2Us

이 문제가 다이나믹 프로그래밍 유형인 이유를 먼저 생각해보자.

2, 3원을 가지고 15원을 만들 수 있는지, 있다면 최소한의 화폐 개수는 몇 개인지 알기 위해서는 어떻게 해야 할까?

 

15원을 만들기 위한 최소한의 화폐 개수를 f(15)라고 하자.

(15원에서 2원을 뺀) 13원과 (3원을 뺀) 12원을 만들 수 있다면, 각각 +2원 or +3원의 과정을 한 번만 더 하면 15원을 만들 수 있을 것이다.

즉, f(15)의 최솟값은 min(f(13), f(12)) + 1원이 된다. 13원일 때의 최소 화폐 개수와 12원일 때의 최소 화폐 개수를 비교하여 거기에 한 번의 연산만 더해준다면 f(15)를 구할 수 있다는 것.

그렇다면 f(13)과 f(12)는 어떻게 구하는가? 이에 대해서도 각각 13원에서 -2, -3원을 해준 값과 12원에서 -2, -3원을 해준 값을 놓고 최소 화폐 개수를 구해주면 되는 것이다. 즉, 문제가 최적의 부분 구조로 나뉜다는 것을 알 수 있다.

또한, 각각의 경우에 대하여 -2, -3을 해줄 경우는 다음과 같은데

f(13) → f(11), f(10)

f(12) → f(10), f(9)

f(10)이 겹치는 게 금방 보인다. 추가로 또 한번 부분 구조를 파헤쳐보면

f(11) → f(9), f(8)

f(10) → f(8), f(7)

f(9) → f(7), f(6)

·

·

·

이런 식으로 부분 문제가 중복되는 것이 보인다. 따라서 다이나믹 프로그래밍의 두 가지 조건을 모두 만족한다.

n, m = map(int, input().split())
arr = [int(input()) for _ in range(n)]

# 최적의 해 담는 리스트 (여기서 최적의 해는 최소 화폐 개수이다)
# 0이 아닌 10001로 초기화해주는 이유는 max값이 아닌 min값을 구해야 하기 때문이다.
# 0으로 초기화한다면 min계산에서 갱신이 되지 않고 계속 0일 것이기 때문에 주의해야 한다.
# m의 범위가 10000까지이므로 inf를 나타내는 수로 10001을 해주면 된다.
d = [10001] * (m + 1) 

d[0] = 0

for i in arr: # 각각의 화폐 단위에 대하여
    for j in range(i, m + 1): # 해당 화폐 단위부터 목표 금액까지 있는 모든 금액에 대하여
        if d[j - i] != 10001: # 해당 금액 - i원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - i] + 1) # 해당 금액까지의 최적의 해를 만드는 방법을 갱신한다.

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