RSS Feed

제켄도르프(Zeckendorf) 표현

Problem 297

출제 일시 : 2020-12-27 00:05:25, ☕ 7

피보나치(Fibonacci) 수열에서 새 항은 이전 두 항의 합으로 생성됩니다.
1과 2로 시작한다면, 첫 10개 항은 1, 2, 3, 5, 8, 13, 21, 34, 55, 89입니다.

모든 자연수는 피보나치 수열의 비연속적인 항의 합으로 고유하게 쓰일 수 있습니다. 예를 들어, 100 = 3 + 8 + 89입니다.
이런 합을 제켄도르프(Zeckendorf) 표현이라 합니다.

n>0이 어떤 정수일 때, z(n)을 n의 제켄도르프 표현의 항의 개수라 합니다.
따라서, z(5) = 1, z(14) = 2, z(100) = 3 등등 입니다.
또한, 0<n<106일 때, z(n) = 7894453입니다.

0<n<1017일 때, z(n) 값을 구하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.