C++로 수열 4, 14, 28, 46, 68, 94, 124, 158...의 N번째 항 구하기

이 문제에서는 하나의 숫자 N이 주어지며, 우리의 과제는 수열 4, 14, 28, 46, 68, 94, 124, 158, ...의 N번째 항을 구하는 C++ 프로그램을 작성하는 것입니다.

문제 설명

주어진 수열의 N번째 항을 찾아야 합니다.

수열: 4, 14, 28, 46, 68, 94, 124, ... (N개의 항)

수열의 일반항(일반식)을 도출한 뒤, N값에 따라 해당 항의 값을 계산하는 방식으로 해결할 수 있습니다.

예시를 통한 문제 이해

입력: N = 5

출력: 68

풀이 접근법

주어진 수열의 일반항을 유도해 보겠습니다. 수열은 다음과 같습니다.

4, 14, 28, 46, 68, 94, 124...

모든 항에서 공통적으로 2가 곱해져 있는 것을 확인할 수 있습니다. 따라서 괄호 안의 부분만 분석하면 됩니다.

수열: 2(2, 7, 14, 23, 34, ...)
= 2((1² + 1), (2² + 3), (3² + 5), (4² + 7), (5² + 9) ...)
= 2((1² + (2-1)), (2² + (4-1)), (3² + (6-1)), (4² + (8-1)), (5² + (10-1)) ...)
= 2((1² + ((2×1)-1)), (2² + ((2×2)-1)), (3² + ((2×3)-1)), (4² + ((2×4)-1)), (5² + ((2×5)-1)) ...)

위 패턴을 일반화하면 수열의 일반항은 다음과 같습니다.

T_n = 2 × (n² + (2n − 1))

이 일반항 공식을 사용하면 수열의 어떤 값이든 손쉽게 계산할 수 있습니다.

검증 예시

N = 6인 경우 직접 계산해 보면 다음과 같습니다.

T6 = 2 × (6² + (2×6 − 1))
   = 2 × (36 + (12 − 1))
   = 2 × (36 + 11)
   = 2 × 47
   = 94

실제 수열의 6번째 항이 94이므로, 도출한 공식이 정확함을 알 수 있습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int findNTerm(int N) {
    int nthTerm = ( 2*((N*N) + ((2*N) - 1)) );
    return nthTerm;
}

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

출력 결과:

11번째 항의 값은 284

코드 설명

findNTerm() 함수는 일반항 공식 T_n = 2 × (n² + 2n − 1)을 그대로 코드로 옮긴 것입니다. N을 제곱한 값에 2N−1을 더하고, 전체에 2를 곱하여 N번째 항을 반환합니다. 이 방식은 반복문 없이 O(1)의 시간 복잡도로 즉시 결과를 얻을 수 있어 매우 효율적입니다.