kthng

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..