boj 2624 : 동전 바꿔주기

boj 2624 : 동전 바꿔주기

https://www.acmicpc.net/problem/2624

이 문제 또한 전형적인 DP문제이다.

나에게는 조금 생소했던... 하지만 이것저것 검색해보니 이문제 또한 전형적인 DP문제라는 것을 알 수 있었다.

이 문제가 만약 동전의 갯수가 주어지지 않았다면 바로 DP로 접근해서 풀었겠지만, 동전의 갯수가 주어져 있으면 DP로 접근하면 해결할 수 없을 것만 같다.

시간복잡도가 엄청 높기 때문이다. (약 T*k*n) 그렇다면 그냥 시간초과 나는게 아닌가? 

일단은 풀린다.

방법은 i번째의 동전으로 table을 채워가는 것. 

초기 세팅은 0원의 경우의 수를 1로 두고 table을 채운다.

1. a[cost][i] i 번째 동전까지의 cost의 경우의 수

2. Pi, ni : i번째 동전의 가격, 갯수

3. a[cost][i] += a[cost - Pi*ki][i - 1] { k = 1 ~ ni}

위와같은 방법으로 1번째, 2번째, 3번째 동전으로 각각 경우의 수를 누적시켜 전체 경우의 수를 계산한다.