• (int)874.38 == 874

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원을 만들 수 없다

• i 수를 제곱수의 합으로 표현 할 수 있는 경우의 수

• 1
  • 1
  • d[1] = 1
• 4
  • 1 + 1 + 1 + 1
  • 4
  • d[4] = 2
• 5
  • 1의 제곱 + 4
    • d[4] = 2
  • 2의 제곱 + 1
    • d[1] = 1
  • d[5] = d[4] + d[1] = 3
  • 여기서 중복 문제가 발생
  • 사실, d[5] = 2