이 튜토리얼에서는 급수 3, 12, 29, 54, 86, 128, 177, 234, ...의 N번째 항을 구하는 프로그램을 작성하는 방법을 알아보겠습니다.
이 문제에서는 하나의 숫자 N이 주어지며, 우리의 목표는 해당 위치에 있는 급수의 항 값을 계산하는 것입니다.
접근 방법
주어진 급수를 자세히 분석해 보면 각 항이 다음과 같은 일반항 공식으로 표현될 수 있습니다.
T(n) = 4n² − 3n + 2
이 공식이 실제로 성립하는지 몇 가지 항으로 검증해 보면 다음과 같습니다.
- n = 1일 때: 4(1)² − 3(1) + 2 = 3
- n = 2일 때: 4(2)² − 3(2) + 2 = 12
- n = 3일 때: 4(3)² − 3(3) + 2 = 29
- n = 4일 때: 4(4)² − 3(4) + 2 = 54
따라서 반복문 없이 주어진 N값에 공식만 대입하면 O(1)의 시간 복잡도로 원하는 항을 즉시 계산할 수 있습니다.
예제 코드
#include <iostream>
#include <math.h>
using namespace std;
// 주어진 급수의 n번째 항 계산
int nthTerm(int n) {
return 4 * pow(n, 2) - 3 * n + 2;
}
int main() {
int N = 4;
cout << nthTerm(N) << endl;
return 0;
}출력 결과
54
코드 설명
위 코드의 nthTerm 함수는 일반항 공식인 4n² − 3n + 2를 그대로 구현한 것입니다. main 함수에서는 N을 4로 설정한 뒤 함수를 호출하여 결과를 출력하며, 실행 결과로 네 번째 항인 54가 출력되는 것을 확인할 수 있습니다.
이처럼 급수의 패턴을 수식으로 일반화하면 불필요한 반복 연산 없이 효율적으로 답을 구할 수 있다는 점이 이 문제의 핵심입니다.