효율적인 화폐 구성

 

문제

주어진 코인을 이용해 문제에서 주어진 돈을 만들어라

 

 

유형 파악 및 구현

전형적인 DP문제인것 같다.

예를 들어 [2, 3]원을 활용해 5원을 만든다고 가정하자.

 

1원 만들 수 있는가? X

2원 만들 수 있는가? O -> 2%2 == 0

3원 만들 수 있는가? O -> 3%3 == 0

4원 만들 수 있는가? O -> 4%2 == 0

5원 만들 수 있는가? O

-> 5%2 ==0 ? X

-> 5%3 ==0 ? X

-> (5-2)원은 만들 수 있는가? == 0? O -> 3원을 만드는 경우의 수 + 1

즉, 5원을 만들때, 2원이나 3원만으로는 만들 수 없다.

하지만 5-2 or 5-3원을 만들 수 있는지 체크 한 후 만들 수 있다면 그 값에 1을 더하면 된다.

 

 

코드

n = 3
result = 10
coins = [2, 3, 5]
INF = 1e9
check = [INF]*(result+1)

for coin in coins:
    check[coin] = 1

for i in range(1, result+1):
    for coin in coins:
        if i % coin == 0:
            check[i] = min(check[i], i//coin)
        if check[i-coin] != INF:
            check[i] = min(check[i], check[i-coin]+1)
    
print(check)