C++에서 주어진 급수의 N번째 항을 구하는 프로그램

이 문제에서는 하나의 숫자 N이 주어지며, C++로 주어진 급수의 N번째 항을 구하는 프로그램을 작성하는 것이 목표입니다.

문제 설명

다음과 같은 급수가 주어졌을 때 −

1, 1, 2, 3, 4, 9, 8, 27, 16, 81, 32, 243, 64, 729, 128, 2187, 256, ... N개의 항

우리는 이 급수의 일반항을 찾아내야 합니다.

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

예제 1

입력

N = 6

출력

9

예제 2

입력

N = 13

출력

64

풀이 접근법

이 문제를 해결하려면 급수를 주의 깊게 관찰해야 합니다. 이 급수는 혼합(mixture) 형태의 수열로, 처음에는 패턴을 인식하기 어렵지만 규칙을 발견하고 나면 비교적 쉽게 다룰 수 있습니다.

이 급수는 다음과 같은 유형의 혼합 급수입니다.

• 홀수 번째 위치: 2의 거듭제곱 수열 (1, 2, 4, 8, 16, ...)
• 짝수 번째 위치: 3의 거듭제곱 수열 (1, 3, 9, 27, 81, ...)

즉, 두 개의 기하급수적 부분 수열이 교대로 배치된 구조입니다. 이를 바탕으로 일반항은 다음과 같이 유도할 수 있습니다.

T_N = 2^N/2, N이 홀수인 경우 (정수 나눗셈)

T_N = 3^(N−1)/2, N이 짝수인 경우 (정수 나눗셈)

예를 들어 N = 13(홀수)이면 2⁶ = 64이고, N = 14(짝수)이면 3⁶ = 729가 됩니다.

예제 코드

#include <iostream>
#include <math.h>
using namespace std;

int findNTerm(int N) {
    if(N % 2 == 0){
        return pow(3, ((N-1)/2));
    }
    else
        return pow(2, (N/2));
}

int main() {
    int N = 9;
    cout<<N<<"th term of the series is "<<findNTerm(N)<<endl;
    N = 14;
    cout<<N<<"th term of the series is "<<findNTerm(N);
}

출력

9th term of the series is 16
14th term of the series is 729

복잡도 분석

이 풀이는 반복문 없이 일반항 공식만으로 답을 계산하므로 시간 복잡도는 O(log N)(거듭제곱 연산 기준)이며, 각 항을 하나씩 계산하는 O(N) 방식보다 훨씬 효율적입니다. 또한 공간 복잡도는 O(1)로 추가적인 메모리가 필요하지 않습니다.