C++로 수열 7, 15, 32, …의 n번째 항 구하기

이 문제에서는 정수 N이 주어지며, 수열 7, 15, 32, ...의 n번째 항을 구하는 것이 목표입니다.

문제 이해를 위한 예시

입력

N = 6

출력

281

설명

n번째 항까지의 수열은 다음과 같습니다.

7, 15, 32, 67, 138, 281

해결 접근 방법

이 문제의 해결 열쇠는 수열의 규칙을 파악하는 데 있습니다. 이 수열은 단순한 등차·등비 수열이 아닌 복합적인 패턴을 가지고 있습니다.

인접한 항들 사이의 차를 구해 보면,

T(2) - T(1) = 15 - 7 = 8
T(3) - T(2) = 32 - 15 = 17

여기서 각 항이 이전 항과 어떤 관계인지 유도할 수 있습니다.

T(2) = 2 * T(1) + 1
T(3) = 2 * T(2) + 2

일반화하면,
T(n) = 2 * T(n-1) + (n-1)

즉, n번째 항의 값은 바로 앞 항을 이용해 계산할 수 있습니다. 따라서 1부터 n까지 반복문을 돌면서 수열의 각 값을 순차적으로 구하면 됩니다.

구현 예제

아래는 위 접근 방식의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int findNthTerm(int n) {
    if (n == 1)
        return 7;
    int termN = 7;
    for (int i = 2; i <= n; i++)
        termN = 2*termN + (i - 1);
    return termN;
}
int main(){
    int n = 12;
    cout<<"The series is 7, 15, 32, 67...\n";
    cout<<n<<"th term of the series is "<<findNthTerm(n);
    return 0;
}

실행 결과

The series is 7, 15, 32, 67...
12th term of the series is 18419

이 프로그램은 첫 번째 항 7을 초기값으로 설정한 뒤, 점화식 T(n) = 2 * T(n-1) + (n-1)을 반복적으로 적용하여 원하는 n번째 항을 효율적으로 계산합니다. 시간 복잡도는 O(n)으로, 반복문 한 번만으로 답을 구할 수 있어 매우 간단하고 효율적인 방법입니다.