수열 1, 6, 15, 28, 45, …의 N번째 항을 구하는 C++ 프로그램

문제 소개

이 문제에서는 하나의 정수 값 N이 주어지며, 우리의 목표는 수열 1, 6, 15, 28, 45, …에서 N번째 항을 찾는 프로그램을 작성하는 것입니다.

이 수열의 흥미로운 성질은 모든 항이 자신의 이전 항과 다음 항의 평균보다 정확히 2만큼 작다는 점입니다.

예제를 통한 문제 이해

입력:

N = 5

출력:

45

해결 접근 방법

수열 1, 6, 15, 28, 45, …의 N번째 항은 다음 공식을 사용하여 간단히 구할 수 있습니다.

TN = 2*N*N - N

이 수열은 인접한 항 사이의 차이가 5, 9, 13, 17처럼 매번 4씩 증가하는 형태이므로, N에 대한 2차 다항식으로 표현할 수 있습니다. 실제로 N=1일 때 2×1−1=1, N=2일 때 2×4−2=6, N=5일 때 2×25−5=45로 공식이 정확히 일치함을 확인할 수 있습니다. 또한 N 값이 커질 때 발생할 수 있는 오버플로를 방지하기 위해 모듈러 연산(mod 1000000009)을 적용했습니다.

구현 예제 코드

#include <iostream>
using namespace std;
#define mod 1000000009
int calcNthTerm(long n) {
    return (((2 * n * n) % mod) - n + mod) % mod;
}
int main(){
    long N = 19;
    cout<<N<<"th Term of the series is "<<calcNthTerm(N);
    return 0;
}

출력 결과:

19th Term of the series is 703

N=19인 경우 공식에 대입하면 2×19×19−19 = 722−19 = 703이 되어, 프로그램의 출력 결과와 일치하는 것을 확인할 수 있습니다.