알고스팟 coin change(coins) 문제 파이썬으로 풀기

금액을 받고, 주어진 동전으로 환전 할 수 있는 경우를 구하는 문제이다.

 

전형적인 동적계획법 문제이다.  처음엔 접근방식을 전체 금액에서 동전을 빼는 식으로 구하려 했다. 즉

금액이 110원이고 동전이 10, 50, 100, 500이 있으면

110=100*1+10*1=50*2+10*1=50*1+10*6=10*11 로 4가지 경우가 나오는데,

110에서 뺄 수 있는 가장 큰 금액인 동전이 100원이므로 110-100=10을 하고, 남은 10에서 뺄 수 있는 가장 금액인 동전이 10이므로 10-10=0 이 되면 횟수에 1을 더하고,

110에서 100을 제외하고 뺄 수 있는 가장 큰 금액인 동전이 50이므로 110-50=60을 하고 여기서 또 가장 큰 금액인 50을 빼서 60-50=10 이 되고, 10-10=0이 되면 횟수 +1,

110에서 50을 한번 빼 60을 만들고, 여기서 또 50을 빼면 윗 경우와 겹치므로 10을 6번 빼서 0을 만들고..

이런식으로 문제를 해결하려 했으나, 코딩을 하면서 에러가 뜨고 결과를 저장하는 것도 어려워서 방향을 바꾸었다.

https://www.youtube.com/watch?v=jaNZ83Q3QGc

그러던 와중 이 동영상을 접하게 되었고, 여기서 나온 방식이 완벽해 보이진 않았지만 이해하기도 쉬웠고, 빠르진 않아보여도 제한시간 내엔 들어갈 거 같아서 나온대로 구현을 해 보았다.

#coins
def coins(money, clist, dp):  # 돈, 동전들, 환전 수를 저장하는 배열을 입력으로 받음
    for o in range(len(coinlist)):  # 동전들 수 만큼
        p = clist[o]
        while p <= money:  # 동전의 금액 부터 전체 돈 까지
            dp[p] += dp[p-clist[o]]  # dp를 한다
            p += 1
 
 
case = int(input())
for i in range(case):
    totalmoney, coinnum = map(int, input().split())  
    coinlist = list(map(int, input().split()))
    coinlist.sort()  # 혹시 모르니 정렬
    dp = [0 for k in range(totalmoney+1)]
    dp[0] = 1  # 환전 할 수 있는 수를 계산하기 위해 totalmoney+1 개의 배열 생성하고, 첫번째 요소를 1로 함
    coins(totalmoney, coinlist, dp)
    result = dp[-1]  # 마지막 요소가 답
    if result > 1000000007:
        result %= 1000000007
    print(result)

 

느낀점:

1. 동적계획법은 역시 어렵다. 기본적인 개념은 이해가 됬는데 실제로 구현을 하면 머리가 하예진다. 연습을 더 해서 나아지기를 빌어야지...

2. 원래 이 문제 말고 ppap(https://algospot.com/judge/problem/read/PPAP)이 문제를 해결하고 싶었는데, 여러가지 갖은 방법을 다 써보았지만 파이썬으로는 정답이 나오질 않았다. c++로는 시간도 얼마 안걸리고 잘 됬는데 왜 파이썬으로 하면 이런지 모르겠다.