이 글에서는 주어진 합을 서로 인접하지 않은 피보나치 수들의 덧셈으로 표현할 수 있는지 확인하고, 가능하다면 어떤 수들인지 찾는 방법을 알아보겠습니다. 예를 들어 주어진 합이 10이라면, 이는 8과 2의 합입니다. 8과 2는 모두 피보나치 수이면서 서로 인접하지 않습니다.
이 문제는 체켄도르프 정리(Zeckendorf's Theorem)와 관련이 있습니다. 체켄도르프 정리에 따르면 모든 양의 정수는 서로 연속되지 않은(인접하지 않은) 피보나치 수들의 합으로 유일하게 표현할 수 있습니다. 핵심 아이디어는 매 단계에서 합보다 크지 않은 가장 큰 피보나치 수를 선택하고, 그 값을 빼가며 반복하는 것입니다.
알고리즘
nonNeighbourFibo(sum)
Begin
while sum > 0, do
fibo := sum보다 크지 않은 가장 큰 피보나치 수
print fibo
sum := sum - fibo
done
End예제 코드
#include<iostream>
using namespace std;
int fibonacci(int n) {
if (n == 0 || n == 1)
return n;
// n보다 작거나 같은 가장 큰 피보나치 수를 구합니다.
int prev = 0, curr = 1, next = 1;
while (next <= n) {
prev = curr;
curr = next;
next = prev + curr;
}
return curr;
}
void nonNeighbourFibo(int sum) {
while (sum > 0) {
int fibo = fibonacci(sum);
cout << fibo << " ";
sum = sum - fibo;
}
}
int main() {
int sum = 120;
cout << "Sum is same as Non-adjacent Fibonacci terms: ";
nonNeighbourFibo(sum);
}실행 결과
Sum is same as Non-adjacent Fibonacci terms: 89 21 8 2
코드 설명
위 코드의 동작 원리를 살펴보겠습니다.
- fibonacci(n) 함수: n보다 크지 않은 가장 큰 피보나치 수를 반환합니다. 세 개의 변수(prev, curr, next)를 사용해 피보나치 수열을 순차적으로 생성하면서 next가 n을 초과하는 순간의 curr 값을 결과로 돌려줍니다.
- nonNeighbourFibo(sum) 함수: sum이 0보다 클 때까지 반복하면서, 현재 sum 이하의 최대 피보나치 수를 찾아 출력하고 sum에서 그 값을 뺍니다.
sum이 120일 때의 동작 과정은 다음과 같습니다.
- 120 이하의 가장 큰 피보나치 수는 89입니다. 남은 값: 120 - 89 = 31
- 31 이하의 가장 큰 피보나치 수는 21입니다. 남은 값: 31 - 21 = 10
- 10 이하의 가장 큰 피보나치 수는 8입니다. 남은 값: 10 - 8 = 2
- 2 이하의 가장 큰 피보나치 수는 2입니다. 남은 값: 2 - 2 = 0
결과적으로 120은 89 + 21 + 8 + 2로 표현됩니다. 각 단계에서 선택된 피보나치 수들이 서로 인접하지 않음을 알 수 있으며, 이것이 바로 체켄도르프 표현법입니다. 이 탐욕(greedy) 알고리즘은 자동으로 연속된 피보나치 수를 선택하지 않기 때문에 항상 유효한 체켄도르프 표현을 보장합니다.