C++ 프로그램으로 수열 2, 10, 30, 68, 130…의 n번째 항 구하기

이 문제에서는 정수 N이 주어지며, 목표는 수열 2, 10, 30, 68, 130, ...의 n번째 항을 구하는 것입니다.

문제 예시

예시를 통해 문제를 쉽게 이해해 보겠습니다.

입력

N = 7

출력

350

설명

수열: 2, 10, 30, 68, 130, 222, 350, ...

해결 접근 방식

가장 간단한 해결 방법은 수열의 일반항, 즉 n번째 항에 대한 공식을 찾는 것입니다. 각 항을 해당 인덱스와 비교해 보면 다음과 같은 규칙성을 발견할 수 있습니다.

i = 1 → T(1) = 2  = 1 + 1  = 1³ + 1
i = 2 → T(2) = 10 = 8 + 2  = 2³ + 2
i = 3 → T(3) = 30 = 27 + 3 = 3³ + 3

즉, 이 수열의 N번째 항은 N³ + N으로 표현됩니다. 각 항은 인덱스의 세제곱에 인덱스 자신을 더한 값과 같습니다.

C++ 구현 코드

위 공식을 적용한 솔루션의 동작을 보여주는 프로그램입니다.

#include <iostream>
using namespace std;

int findNthTerm(int N) {
    return ((N * N * N) + N);
}

int main() {
    int N = 8;
    cout << "수열의 " << N << "번째 항은 " << findNthTerm(N) << "입니다";
    return 0;
}

실행 결과

수열의 8번째 항은 520입니다

마무리

이처럼 수열의 규칙성을 분석해 일반항을 도출하면, 반복문 없이 O(1)의 시간 복잡도로 n번째 항을 즉시 계산할 수 있습니다. N³ + N 공식만 기억하면 아무리 큰 N 값이 주어져도 빠르고 정확하게 답을 구할 수 있습니다.