9009 - 피보나치
문제
피보나치 수 ƒK는 ƒK = ƒK-1 + ƒK-2로 정의되며 초기값은 ƒ0 = 0과 ƒ1 = 1 이다. 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실은 잘 알려져 있다.
하나의 양의 정수에 대한 피보나치 수들의 합은 여러 가지 형태가 있다.
예를 들어 정수 100은 ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 또는 ƒ1 + ƒ3 + ƒ6 + ƒ11 = 1 + 2 + 8 + 89, 또는 ƒ4 + ƒ6 + ƒ9 + ƒ10 = 3 + 8 + 34 + 55 등으로 나타낼 수 있다.
이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다.
하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라.
코드
한마디
입력하는 정수 n을 10억까지로 제한해줬기 때문에 매 반복문마다 피보나치 수열을 계산하지 않고, 미리 리스트로 만들어놨다. 50까지 돌린 경우 약 70억 정도의 수가 나왔다. 조금 더 정확히 하고싶다면 45까지로 제한하여 피보나치 수열을 만들면 된다.