제곱 동전
면접 대비시간 제한2초메모리 제한512 MB
300 미만의 각 금액을 제곱수 값의 동전(1, 4, 9, ..., 289)들의 합으로 나타내는 방법의 수를 순서를 구분하지 않고 센다.
문제
실버랜드 사람들은 제곱 동전을 사용한다. 동전의 모양이 정사각형일 뿐만 아니라 액면가도 제곱수이다. 실버랜드에서는 289(= 17^2) 이하의 모든 제곱수에 해당하는 액면가의 동전, 즉 1 크레딧 동전, 4 크레딧 동전, 9 크레딧 동전, ..., 289 크레딧 동전을 사용할 수 있다.
10 크레딧을 지불하는 조합은 네 가지이다.
- 1 크레딧 동전 열 개
- 4 크레딧 동전 하나와 1 크레딧 동전 여섯 개
- 4 크레딧 동전 두 개와 1 크레딧 동전 두 개
- 9 크레딧 동전 하나와 1 크레딧 동전 하나
주어진 금액을 실버랜드의 동전으로 지불하는 방법의 수를 세는 것이 여러분의 임무이다.
입력
입력은 지불할 금액을 나타내는 정수가 한 줄에 하나씩 주어지고, 그 뒤에 0이 포함된 줄이 온다. 모든 금액은 양수이고 300보다 작다고 가정할 수 있다.
출력
각 금액에 대해 동전 조합의 수를 나타내는 정수 하나를 한 줄에 출력한다. 출력에는 다른 문자도 나타나서는 안 된다.