C++로 구현하는 N번째 트리보나치 수 계산 방법

값 n이 주어졌을 때, n번째 트리보나치(Tribonacci) 수를 구하는 문제를 살펴보겠습니다. 트리보나치 수는 피보나치 수와 유사하지만, 다음 항을 만들 때 이전 두 항이 아닌 세 개의 이전 항을 더한다는 점이 다릅니다.

n번째 항 T(n)을 구하는 공식은 다음과 같습니다.

T(n) = T(n - 1) + T(n - 2) + T(n - 3)

수열은 {0, 1, 1}에서 시작하며, 그 뒤의 항들은 앞의 세 항을 모두 더한 값이 됩니다. 예를 들어 네 번째 항은 0 + 1 + 1 = 2, 다섯 번째 항은 1 + 1 + 2 = 4가 됩니다.

알고리즘

반복문을 사용해 세 개의 변수만 유지하면서 효율적으로 계산할 수 있습니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.

• first := 0, second := 1, third := 1 로 초기화
• i가 0부터 n - 3까지 반복:
    o next := first + second + third
    o first := second, second := third, third := next
• third 반환

C++ 예제 코드

#include<iostream>
using namespace std;

long tribonacci_gen(int n){
    // n번째 트리보나치 수를 생성하는 함수
    int first = 0, second = 1, third = 1;
    for(int i = 0; i < n - 3; i++){
        int next = first + second + third;
        first = second;
        second = third;
        third = next;
    }
    return third;
}

int main(){
    cout << "15th Tribonacci Term: " << tribonacci_gen(15);
}

입력

15

출력

15th Tribonacci Term: 1705

위 코드에서 n = 15를 입력하면 15번째 트리보나치 수인 1705가 출력됩니다. 이처럼 세 개의 변수만 갱신해 나가면 추가 배열 없이도 선형 시간 안에 원하는 항을 구할 수 있습니다.