C++로 수열 3, 13, 42, 108, 235...의 n번째 항 구하기

이 문제에서는 하나의 숫자 n이 주어지며, 우리의 목표는 수열 3, 13, 42, 108, 235...의 n번째 항을 구하는 것입니다.

문제 이해를 위한 예시

입력 : 5
출력 : 235

해결 접근 방법

이 수열은 첫 n개의 자연수를 세제곱한 값들의 합으로 표현할 수 있습니다. 자연수 세제곱의 합 공식은 다음과 같습니다.

(n * (n + 1) / 2)²

여기서 주목할 점은 이 수열의 각 항이 해당 세제곱의 합보다 정확히 2 * n만큼 크다는 것입니다. 따라서 위 공식에 2 * n을 더하면 원하는 수열의 일반항을 얻을 수 있습니다.

수열의 일반항 공식

(n * (n + 1) / 2)² + 2 * n

n = 5인 경우 공식에 대입하여 직접 확인해 보겠습니다.

(5 * (5 + 1) / 2)² + 2 * 5

= (5 * 6 / 2)² + 10

= (15)² + 10

= 225 + 10

= 235

계산 결과가 수열의 5번째 항인 235와 일치하므로, 이 공식이 올바르다는 것을 알 수 있습니다.

구현 예제

다음은 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int findNthTerm(int N)
{
   return ((N * (N + 1) / 2) * (N * (N + 1) / 2)) + 2 * N;
}
int main()
{
   int N = 5;
   cout << "수열의 " << N << "번째 항은 " << findNthTerm(N);
   return 0;
}

실행 결과

수열의 5번째 항은 235

복잡도 분석

이 풀이법은 곱셈과 나눗셈 연산만 사용하므o 시간 복잡도는 O(1)이며, 추가적인 메모리도 필요하지 않습니다. 반복문 없이 단 한 번의 계산으로 n번째 항을 구할 수 있어 매우 효율적입니다.