이 문제에서는 정수 N이 주어졌을 때, C++ 프로그램을 이용해 N번째 비피보나치 수(Non-Fibonacci Number), 즉 피보나치 수열에 속하지 않는 N번째 수를 구하는 것이 목표입니다.
피보나치 수열의 기본 개념
피보나치 수열은 앞의 두 수를 더해 다음 수를 만들어 가는 수열입니다. 수열은 F0과 F1이라는 두 초기값에서 시작하며, 초기값은 일반적으로 0과 1 또는 1과 1로 설정합니다.
문제 예시
입력:
N = 5
출력:
10
설명: 피보나치 수열에 포함되지 않는 수는 4, 6, 7, 9, 10, 11, 12, … 순서로 나열됩니다. 이 중 다섯 번째 수는 10입니다.
해결 접근 방법
가장 단순한 방법은 피보나치 수를 모두 구한 뒤, 피보나치 수에 해당하지 않는 처음 N개의 수를 차례로 세는 것입니다.
더 효율적인 방법은 피보나치 수의 성질을 활용하는 것입니다. 연속된 두 피보나치 수 사이에는 일정 개수의 비피보나치 수가 존재하므로, 이 간격(gap)을 누적해 더해 가면 원하는 답을 빠르게 구할 수 있습니다. 여기서는 후자의 방법을 사용합니다.
알고리즘
- 현재 값(currVal), 직전 값(lastVal), 두 단계 전 값(lastLastVal)을 추적하는 세 개의 변수를 준비합니다.
- 세어야 할 비피보나치 수가 남아 있는 동안(n > 0), 피보나치 수의 기본 공식인 Fib(n) = Fib(n-1) + Fib(n-2)를 이용해 수열을 전진시킵니다.
- 공식 n = n + (currVal - lastVal - 1)을 통해 두 피보나치 수 사이에 존재하는 비피보나치 수의 개수를 반영합니다.
- 루프가 끝나면 초과로 감소된 n을 다시 보정한 뒤, 직전 피보나치 수에 n을 더해 N번째 비피보나치 수를 구합니다.
C++ 구현 예제
다음은 위 해결 방법의 동작을 보여 주는 프로그램입니다.
#include<iostream>
using namespace std;
int findNthNonFiboNumber(int n){
int lastLastVal = 1, lastVal = 2, currVal = 3;
while (n > 0){
lastLastVal = lastVal;
lastVal = currVal;
currVal = lastLastVal + lastVal;
n = n - (currVal - lastVal - 1);
}
n = n + (currVal - lastVal - 1);
return (lastVal + n);
}
int main(){
int n = 7;
cout<<"Nth non fibonacci number is "<<findNthNonFiboNumber(n);
return 0;
}실행 결과
Nth non fibonacci number is 12
위 코드에서는 N = 7을 입력했으며, 일곱 번째 비피보나치 수인 12가 정상적으로 출력됩니다.