coins

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

풀이

• 9084 번 문제와 동일한 문제

• ex)

  

• d[i] : i원을 만드는 경우의 수

  • 2원으로 i 만드는 경우의 수 + 3원으로 i 만드는 경우의 수 + 5원으로 i 만드는 경우의 수

• 목표금액 7원을 만드는 경우

  • 2원으로 만드는 경우 : 위 표와 같다

  • 3원으로 만드는 경우 : 이전 결과에 경우의 수를 더한다.

    • money가 6원 일 때

      • 2원 * 3개 (이전 결과)
      • 3원 * 2개

    • money가 7원 일 때

      • 2원 * 2개 + 3원 * 1개

• X 의 의미

  • 2원으로 1원을 만들 수 없다
  • 3원으로 1원, 2원을 만들 수 없다
  • 5원으로 1원, 2원, 3원, 4원을 만들 수 없다