BOJ/2293_동전1

[문제]

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

[처음 생각]

쿠팡 알고리즘 시험에서 2번 문제로 나왔던 문제와 똑같다. 그때 검색으로 풀어서 답은 맞았지만 다시 주면 못풀것 같아서 다시 풀어보려 한다...

생각해봐도 그냥 for문으로 돌리는것말고는 dp로 잘 모르겠음... 점화식이 안세워짐 ㅜㅜ 

[풀이]

dp[i] 를 i원을 만들기 위한 경우의 수 배열로 생성한다.

예제를 사용해서 설명한다면...

dp[10]은 dp[9]에 1원을 더한 것과 dp[8]에 2원을 더한 것과 dp[5]에 5원을 더한 것의 합과 같다.

dp[10] = dp[9] + dp[8] + dp[5]

이렇게 dp[9]와 dp[8], dp[5]를 마찬가지 방법으로 분해해서 생각한다.

계속 쪼갰을 때 점화식 dp[k] = dp[k] + dp[k - coins[i]] 를 세울 수 있다. 

[참고]

http://dyndy.tistory.com/194

[Code]

https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_2293/Coin1.java