C++로 수열 3, 9, 21, 41, 71…의 n번째 항 구하기

문제 개요

이 문제에서는 정수 N이 하나 주어지며, 수열 3, 9, 21, 41, 71...의 n번째 항을 구하는 것이 목표입니다.

예시를 통해 문제를 살펴보겠습니다.

입력

N = 7

출력

169

설명

수열: 3, 9, 21, 41, 71, 113, 169...

해결 접근 방법

이 문제를 해결하는 가장 효율적인 방법은 수열의 일반항을 찾는 것입니다. 먼저 인접한 항들 사이의 차이를 관찰해 보겠습니다.

• 9 − 3 = 6
• 21 − 9 = 12
• 41 − 21 = 20
• 71 − 41 = 30

차이 값이 6, 12, 20, 30처럼 규칙적으로 증가하는 것으로 보아 이 수열은 2차식(n² 항을 포함하는 식)으로 표현할 수 있습니다. 실제로 일반항은 다음과 같습니다.

T(N) = Σn² + Σn + 1

즉, 처음 n개 자연수의 제곱합과 처음 n개 자연수의 합을 구한 뒤 1을 더하면 됩니다. 잘 알려진 합 공식을 대입하면 다음과 같은 닫힌 형태의 공식을 얻을 수 있습니다.

T(N) = [n × (n+1) × (2n+1) / 6] + [n × (n+1) / 2] + 1

이 공식을 활용하면 반복문 없이 O(1)의 시간 복잡도로 n번째 항을 즉시 계산할 수 있어 매우 효율적입니다.

구현 예제

#include <iostream>
using namespace std;
int findNthTerm(int n) {
    return ((((n)*(n + 1)*(2*n + 1)) / 6) + (n * (n + 1) / 2) + 1);
}
int main() {
    int N = 12;
    cout<<"The "<<N<<"th term of the series is "<<findNthTerm(N);
    return 0;
}

실행 결과

The 12th term of the series is 729

동작 원리 정리

위 프로그램은 수열의 패턴을 분석해 일반항을 도출한 뒤, 공식에 값을 대입하여 바로 결과를 계산합니다. 예를 들어 N=12일 경우 제곱합은 650, 자연수의 합은 78이므로 650 + 78 + 1 = 729가 되어 12번째 항이 정확하게 출력됩니다. 이처럼 일반항 공식을 활용하면 어떤 큰 N 값에 대해서도 빠르게 답을 구할 수 있습니다.