C++로 f[i] = f[i-1] - f[i-2] 규칙의 수열에서 N번째 항 구하기

문제 개요

다음과 같은 규칙을 따르는 수열 f가 있다고 가정해 보겠습니다.

f[i] = f[i – 1] – f[i – 2]

첫 번째 항은 f[0] = X, 두 번째 항은 f[1] = Y로 주어지며, 목표는 이 수열의 N번째 항을 구하는 것입니다. 예를 들어 X = 2, Y = 3, N = 3이라면 결과값은 -2가 됩니다.

핵심 아이디어: 수열의 주기성

이 수열을 자세히 관찰해 보면 흥미로운 패턴을 발견할 수 있습니다. 바로 여섯 개의 항을 주기로 수열이 반복된다는 점입니다.

X = 2, Y = 3일 때 앞의 여섯 항을 직접 계산해 보면 다음과 같습니다.

• f[0] = 2
• f[1] = 3
• f[2] = 3 – 2 = 1
• f[3] = 1 – 3 = -2
• f[4] = -2 – 1 = -3
• f[5] = -3 – (-2) = -1

그리고 f[6] = -1 – (-3) = 2, f[7] = 2 – (-1) = 3으로 다시 처음 패턴으로 돌아오는 것을 확인할 수 있습니다.

따라서 N번째 항까지 일일이 계산할 필요 없이, 처음 6개 항만 구한 뒤 N mod 6번째 항을 반환하면 됩니다. 이 방법의 가장 큰 장점은 N이 아무리 커도 상수 시간(O(1)) 안에 답을 구할 수 있다는 점입니다.

C++ 구현 코드

#include <iostream>
using namespace std;

int searchNthTerm(int x, int y, int n) {
    int terms[6];
    terms[0] = x;
    terms[1] = y;
    for (int i = 2; i <= 5; i++)
        terms[i] = terms[i - 1] - terms[i - 2];
    return terms[n % 6];
}

int main() {
    int x = 2, y = 3, n = 3;
    cout << "Term at index " << n << " is: " << searchNthTerm(x, y, n);
}

실행 결과

Term at index 3 is: -2

코드 설명 및 정리

위 코드는 길이 6짜리 배열에 초기 두 항(X, Y)을 저장한 뒤, 점화식을 이용해 세 번째부터 여섯 번째 항까지 채웁니다. 이후 n % 6 연산으로 배열에서 해당 위치의 값을 반환하기만 하면 됩니다.

이러한 주기성이 성립하는 이유는 이 점화식의 특성 방정식 t² − t + 1 = 0의 해가 복소수이고, 그 거듭제곱이 정확히 6을 주기로 순환하기 때문입니다. 이처럼 반복되는 패턴을 미리 파악해두면 아주 큰 N 값에 대해서도 효율적으로 N번째 항을 계산할 수 있습니다.