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