C++로 수열 3, 14, 39, 84…의 N번째 항 구하는 프로그램

이 문제에서는 하나의 정수 N이 주어지며, 수열 3, 14, 39, 84…의 N번째 항을 찾는 프로그램을 작성해야 합니다.

문제 이해를 위한 예시

입력

N = 4

출력

84

설명

수열의 4번째 항은 다음과 같이 계산됩니다.
(4 × 4 × 4) + (4 × 4) + 4 = 64 + 16 + 4 = 84

즉, 각 항은 해당 위치 값 N에 대해 N³ + N² + N으로 표현할 수 있습니다. 실제로 1번째 항은 1+1+1=3, 2번째 항은 8+4+2=14, 3번째 항은 27+9+3=39로 수열과 정확히 일치합니다.

해결 접근 방식

이 문제를 해결하는 가장 간단하고 효율적인 방법은 수열의 N번째 항에 대한 일반 공식을 사용하는 것입니다.

N번째 항 = (N × N × N) + (N × N) + N

반복문 없이 단순 연산만으로 결과를 얻을 수 있으므로 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)로 매우 효율적입니다.

C++ 구현 예제

#include <iostream>
using namespace std;

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

int main() {
    int N = 6;
    cout << N << "번째 항의 값은 " << calcNthTerm(N);
    return 0;
}

출력

6번째 항의 값은 258

위 프로그램은 N=6일 때 6³ + 6² + 6 = 216 + 36 + 6 = 258을 계산하여 올바른 결과를 출력합니다. 이처럼 일반항 공식을 활용하면 어떤 큰 N 값에 대해서도 즉각적으로 답을 구할 수 있습니다.