동전

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

풀이

• ex) 1원, 5원, 10원이 있다. 만들어야하는 동전은 100원

• 1원을 이용해서

    d[1] : 1원을 만드는 경우의 수 => 1원, d[0] => 1
  

  ​ d[2] : 2원을 만드는 경우의 수 => 1원, d[1] => 1
  ​ d[3] : 3원을 만드는 경우의 수 => 1원, d[2] => 1
  ​ …
  ​ d[100] : 100원을 만드는 경우의 수 => 1원, d[99] => 1

• 5원을 이용해서

    d[5] : 5원을 만드는 경우의 수 => (1원, d[4]) + (5원, d[0]) => 1 + 1 => 2
  

  ​ d[6] : 6원을 만드는 경우의 수 => 1원, d[5] => 1
  ​ d[7] : 7원을 만드는 경우의 수 => 5원, d[2] => 1
  ​ …
  ​ d[9] : 9원을 만드는 경우의 수 => (1원,d[8]) + (5원, d[5])
  ​ …
  ​ d[100]

• 10원을 이용해서
  ​

    d[10] : 10원을 만드는 경우의 수 => (1원,d[9]) + (5원, d[5]) + (10원, d[0])
  

  ​ …
  ​ d[100]

• 위와 같이 전 단계에 나온 결과값을 재사용할 수 있다. 때문에 DP 문제이다.

​

​
​