[이것이 코딩 테스트다] 효율적인 화폐 구성 - 다이나믹 프로그래밍

이 문제는 대학교 1학년 때 공부했던 이산수학에서 다룬 문제여서 금방 풀 수 있었다.

그때 문제도 마찬가지로 2와 3의 화폐로 모든 화폐를 표현할 수 있냐는 문제였던 것 같다.

2, 3, 2+2, 2+3, 3+3, ... 1 이하의 정수를 제외한 모든 화폐를 표현할 수 있었다.

 

문제의 입력 조건으로는 최대 입력이 100이라서 O(n^2) 으로도 충분하다. 그래서 2중 for문을 채택했다.

 

최소 화폐 단위가 2, 3, 7이라고 가정하자. 그러면

a[i]를 위 화폐 단위로 만들 수 있을 때, a[i](최소 화폐 개수)는 min(a[i], a[i - 2]+1, a[i - 3]+1, a[i - 7]+1) 이다.

이것은 이해를 돕기위해 세운 약간 어거지(?) 점화식이다. 실제로는 각 화폐 단위를 하나 씩만 비교하여 따진다.

 

일반화를 해보면,

최소 화폐 단위 중 k가 있다.

a[i-k]를 만드는 방법이 존재하는 경우, a[i] = min(a[i - k] + 1, a[i]) 이다.

 

*그런데 i-7 과 같은 연산을 하면서 index가 바깥으로 튈 수도 있다. (파이썬은 list[-1] 과 같은 인덱싱이 가능하다.)

* index out of range error는 아니지만, 결국에 우리의 논리적 오류로 이끌 수도 있으므로, 유의가 필요하다.

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

dp = [10**7] * 10001
for mny in money:
    dp[mny] = 1
    for j in range(mny, 10001):
        dp[j] = min(dp[j-mny]+1, dp[j])
print(dp[1:])
print(k if (k:=dp[m]) != 10**7 else -1)

나는 dp table을 0이 아닌 10**7로 채웠다. min연산을 할 때 부가적인 작업을 하지 않아도 되기 때문이다.

dp table에 마지막까지 10**7로 남는 경우는 결국 입력받은 화폐 단위로는 만들 수 없는 수라는 의미이다.

---

    for j in range(mny, 10001, mny):
        dp[j] = min(dp[j-mny]+1, dp[j])

처음에는 에라토스테네스의 체에서 영감을 받아서 문제를 해결하려고 했다. 그래서 range의 증가폭도 설정했다. 그랬더니 원치 않는 결과가 나와서 얼른 살피고 옳게 코드를 수정했다.