이 글에서는 수열 2, 6, 12, 20, 30…의 첫 N항 합을 구하는 방법을 알아봅니다. 합을 계산하기에 앞서 가장 먼저 해야 할 일은 수열의 규칙성을 파악하는 것입니다.
수열의 패턴 분석
각 항을 자세히 살펴보면 다음과 같이 두 부분으로 나눌 수 있습니다.
(1+1), (2+4), (3+9), (4+16)…
즉, (1+1²), (2+2²), (3+3²), (4+4²)…
따라서 이 수열은 두 개의 기본 수열로 분해할 수 있습니다.
- S1: 1, 2, 3, 4, 5… (자연수 수열)
- S2: 1², 2², 3², 4²… (자연수의 제곱 수열)
수학 공식으로 합 구하기
두 수열의 합은 잘 알려진 공식을 이용해 반복문 없이 간단히 계산할 수 있습니다.
Sum1 = 1 + 2 + 3 + 4 + … = n(n+1)/2
Sum2 = 1² + 2² + 3² + 4² + … = n(n+1)(2n+1)/6
전체 합은 두 공식의 결과를 더한 값입니다.
합계 = n(n+1)/2 + n(n+1)(2n+1)/6
C 프로그램 예제
#include <stdio.h>
int main() {
int n = 3;
int sum = ((n * (n + 1)) / 2) + ((n * (n + 1) * (2 * n + 1)) / 6);
printf("첫 %d항까지 수열의 합은 %d입니다", n, sum);
return 0;
}
실행 결과
첫 3항까지 수열의 합은 20입니다
n = 3일 때 직접 검증해 보면 2 + 6 + 12 = 20으로 결과가 정확히 일치합니다.
시간 복잡도
이 방법은 반복문 없이 수학 공식만 사용하므로 시간 복잡도가 O(1)입니다. 각 항을 하나씩 더하는 반복문 방식(O(n))보다 훨씬 효율적이며, N이 아무리 커져도 즉시 결과를 얻을 수 있다는 장점이 있습니다.