우리나라 화폐는 아래와 같이 1원 동전부터 5만원권 지폐까지 모두 10가지가 있습니다.

1원, 5원, 10원, 50원, 100원, 500원, 1000원, 5000원, 10000원, 50000원

우리나라 돈으로 10만원을 지불하는 방법은 모두 몇 가지가 있을까요?

이 문제를 풀기 위해서는 간단하게 코딩하여 9중 루프를 쓰거나, 미모이제이션과 함께 재귀 함수를 쓰기도 하고
코딩 문제를 많이 풀어 보신 분은 흔히 DP라고 알려진 동적계획법을 사용합니다.
이렇게 풀면 10만원을 지불하는 방법은 모두 73905621698546408 가지가 있음을 알 수 있습니다.

좀 더 좋은 풀이는 없을까요?
만일 사용할 수 있는 화폐가 1원과 5원 뿐이라면 금액 m원을 지불하는 가지수 $f_{5}(m)$은 아래와 같이 닫힌 형태의 공식으로 구할 수 있습니다.
$$f_{5}(m) = \lfloor (m + 5)/5 \rfloor$$ 게다가 금액 m원이 5원의 배수라면 바닥/절사 함수도 제거할 수 있습니다. 비슷하게, 사용할 수 있는 화폐가 1원, 5원, 10원 뿐일 때, 10원의 배수인 금액 $m$원을 지불하는 가지수 $f_{10}(m)$은 아래의 닫힌 형태의 공식으로 정확히 구할 수 있습니다.
$$f_{10}(m) = (m^2 + 20 m + 100)/100$$ 사실 우리나라 화폐 10가지를 모두 써서 5만원의 배수인 금액 $m$원을 지불하는 가지수 $f_{50000}(m)$은 다음 9차 다항식으로 표현가능합니다.
$$f_{50000}(m) = (m^9 + a_1 m^8 + a_2 m^7 + a_3 m^6 + ... + a_8 m + a_9)/a_9 $$
$\Sigma_{k=1}^{9} |a_k|$ 값을 구하고 $10^{10}$로 나눈 나머지를 제출하세요.

출처) 사이냅소프트 2011년 휴가철 특집 프로그래밍 연습 8번 화폐