[Algorithm] Bank Problem (동전 문제)

0. 문제

codetree의 은행 문제이다. link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-modeling-bank/description

코드트리

유료 사이트이긴 하지만 자료구조 개념을 정리하기 유용하다. 코딩 테스트, cs 면접을 준비한다면 추천한다. 

 

가치가 1, 4, 5, 9개인 4개의 동전이 있을 때, 주어진 금액 n을 거슬러주기 위한 필요한 최소 동전의 수를 구해보려고 한다.

 

1. 풀이

 

Dynamic Programming (동적 계획법) 을 이용한 문제다. 간단히 설명하면, 하나의 문제를 여러 문제로 쪼갠 뒤, 쪼개진 문제의 해답을 이용해 최종적인 답을 얻는 것이다. 

 

여기서 문제를 쪼개자면, 핵심은 나를 선택하느냐 선택하지 않느냐이다.

동전의 입장에서 나를 선택하여 지불할지, 아닐지를 선택해야 한다. 

따라서 k가 동전의 금액이라면, n-k원을 지불하는 방법에 1을 더한 것과 나를 선택하지 않는 경우를 비교해야 할 것이다.

이를 점화식으로 표현하면 다음과 같다.

dp[i]: i를 지불하는 방법 중 동전을 가장 적게 쓰는 방법

coin[j]: j번째 동전의 금액

dp[i] = min(dp[i-coin[j]]+1, dp[i])

 

2. 구현

 

coin = [1, 4, 5, 9]
n = int(input())
dp = [n+1 for _ in range(n+1)]
dp[0] = 0

for i in range(n+1):
    for j in range(len(coin)):
        if i - coin[j] >= 0:
            dp[i] = min(dp[i], dp[i-coin[j]] + 1)

print(dp)

dp는 나올 수 없는 값, 즉 모두 1원으로 지불했을 때의 가짓수에서 하나를 더한 값으로 설정한다.

그래야 값을 지불할 수 없는 경우를 나타낼 수 있기 때문이다.

보통 dp의 초기값은 나올 수 없는 값으로 설정한다.

 

i가 coin의 금액보다 작을 수 있으므로 조건문을 걸어주고, 해당 점화식을 실행한다.