백준 [java 자바] 9084 : 동전

 

 

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

9084번: 동전

 

이 문제를 보자마자 언젠가 풀었던 문제인 것 같은데? 라는 생각이 들긴 했다. dp를 사용하고, 점화식을 구해서 풀어야 한다는 것 까지는 알아냈지만 여기서 어떻게 해야 할지 도저히 감이 잡히지 않아서 사람들의 풀이법을 검색해서 배웠다.

일단 풀이법을 그림으로 정리해보았다. 글씨가 정말 별로지만, 이해하는데는 확실히 도움이 되었다. 일단, 동전의 수가 주어지고 동전의 액수가 들어오면, 해당 액수만큼 dp배열을 만든다. 

그 다음에 동전의 액수가 작은 것 부터 하나씩 탐색하는데, 현재 탐색중인 액수에서, 현재 탐색중인 동전의 액수만큼 뺀 것을 액수의 dp값에 더해주면, 이제까지 탐색했던 동전들로 만들 수 있는 종류의 수가 배열에 들어가게된다.