C++에서 수열 9, 23, 45, 75, 113…의 N번째 항을 구하는 프로그램

이 문제에서는 수열의 n번째 항을 나타내는 정수 n이 하나 주어집니다. 우리가 작성해야 할 프로그램은 C++를 이용해 수열 9, 23, 45, 75, 113…의 N번째 항을 구하는 것입니다.

문제 설명

주어진 수열의 일반항을 먼저 찾아낸 뒤, 그 식을 이용해 n번째 항을 계산해야 합니다.
대상 수열은 다음과 같습니다.

9, 23, 45, 75, 113, 159, 213, …

예시로 이해하기

• 입력: n = 5
• 출력: 159

해결 접근 방법

주어진 수열의 일반항은 다음과 같습니다.

N번째 항 = (2×N + 3)² − 2×N

이 수열의 규칙을 자세히 살펴보면, 각 항은 연속된 홀수의 제곱에서 짝수를 뺀 형태임을 알 수 있습니다. 즉, 3², 5², 7², 9², 11²… 에서 차례대로 0, 2, 4, 6, 8… 을 빼면 9, 23, 45, 75, 113… 이라는 수열이 만들어집니다.

이러한 일반항 공식을 활용하면 반복문 없이 단 한 번의 연산만으로 N번째 항을 바로 구할 수 있으며, 시간 복잡도는 O(1)로 매우 효율적입니다.

구현 예제

#include <iostream>
using namespace std;
int calcNTerm(int N) {
   int nthTerm = ( (2*N + 3)*(2*N + 3) - (2*N) );
   return nthTerm;
}
int main() {
   int n = 6;
   cout<<"Nth term of the series is "<<calcNTerm(n);
   return 0;
}

출력 결과:

Nth term of the series is 213

n = 6을 공식에 대입해 보면 (2×6 + 3)² − 2×6 = 15² − 12 = 225 − 12 = 213으로, 프로그램의 실행 결과와 정확히 일치하는 것을 확인할 수 있습니다.