C++로 구현하는 수열 5, 13, 25, 41, 61…의 N번째 항 찾기

이 문제에서는 정수 N이 주어지며, 수열 5, 13, 25, 41, 61, …의 N번째 항을 구하는 프로그램을 C++로 작성하는 것이 목표입니다.

문제 이해를 위한 예시

입력

N = 5

출력

61

설명

주어진 수열은 5, 13, 25, 41, 61… 순서로 진행되며, 5번째 항은 61입니다.

해결 접근 방법

이 문제를 가장 간단하게 해결하는 방법은 수열의 일반항 공식을 활용하는 것입니다. 먼저 인접한 항 사이의 차이를 살펴보면 8, 12, 16, 20처럼 매번 4씩 증가하는 패턴을 보입니다. 이러한 규칙성은 2차 다항식으로 표현되는 수열의 전형적인 특징입니다.

따라서 N번째 항은 다음 공식으로 계산할 수 있습니다.

N번째 항 = (N × N) + ((N+1) × (N+1)) = 2N² + 2N + 1

공식을 검증해 보면, N=1일 때 1+4=5, N=2일 때 4+9=13, N=3일 때 9+16=25로 실제 수열과 정확히 일치합니다. 또한 이 방법은 반복문 없이 단 한 번의 연산으로 답을 구하므로 시간 복잡도가 O(1)이라는 장점이 있습니다.

구현 예제 코드

#include <iostream>
using namespace std;
int calcNthTerm(int N) {
    return ( ( (N + 1)*( N + 1) ) + (N*N) ) ;
}
int main() {
    int N = 7;
    cout<<N<<"th term of the series is "<<calcNthTerm(N);
    return 0;
}

실행 결과

7th term of the series is 113

위 코드에서 calcNthTerm 함수는 일반항 공식을 그대로 구현한 것으로, N=7을 입력하면 (7×7) + (8×8) = 49 + 64 = 113이 출력됩니다. 이처럼 수열의 패턴을 분석하여 일반항을 도출하면 어떤 큰 N에 대해서도 즉시 답을 계산할 수 있습니다.