C++로 구하는 수열의 합: 1 + (1+3) + (1+3+5) + ... + (1+3+...+(2n-1))

이 문제에서는 정수 n이 주어지며, 우리의 목표는 다음과 같은 수열의 합을 구하는 프로그램을 작성하는 것입니다.

1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+...+(2n-1))

이 수열을 잘 살펴보면, i번째 항은 첫 번째 홀수부터 i번째 홀수까지의 합, 즉 '처음 i개의 홀수의 합'이라는 규칙을 발견할 수 있습니다.

예제로 문제 이해하기

입력

n = 3

출력

설명 − (1) + (1+3) + (1+3+5) = 14

방법 1: 중첩 루프를 이용한 단순 해결법

가장 직관적인 방법은 중첩 루프(nested loop)를 사용하는 것입니다. 바깥 루프는 각 항을 순회하고, 안쪽 루프는 해당 항을 구성하는 홀수들을 더하며, 그 결과를 sum 변수에 누적한 후 최종 합을 반환합니다.

코드 예제

#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
    int sum = 0, element = 1;
    for (int i = 1; i <= n; i++) {
        element = 1;
        for (int j = 1; j <= i; j++) {
            sum += element;
            element += 2;
        }
    }
    return sum;
}
int main() {
    int n = 12;
    cout<<"Sum of the series 1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+ ... + (2*"<<n<<"-1)) is "<<calcSeriesSum(n);
    return 0;
}

출력

Sum of the series 1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+ ... + (2*12-1)) is 650

이 방법은 두 개의 중첩 루프를 사용하기 때문에 시간 복잡도가 O(n²)으로 비효율적입니다. 입력 크기가 커질수록 실행 시간이 급격히 늘어나므로 더 나은 접근 방식이 필요합니다.

방법 2: 수학적 공식을 이용한 효율적인 해결법

더 효율적인 방법은 수열의 일반항을 수학적으로 유도하여 공식화하는 것입니다.

먼저, 처음 n개의 홀수의 합은 잘 알려진 공식에 따라 다음과 같습니다.

1 + 3 + 5 + ... + (2n-1) = n²

이제 전체 수열의 합을 구해 보겠습니다.

sum = (1) + (1+3) + (1+3+5) + … + (1+3+5+ … + 2n-1)
sum = ∑ (1+3+5+ … + 2i-1)
sum = ∑ i²
sum = [n * (n+1) * (2*n + 1)] / 6

즉, 각 항이 i²이므로 전체 합은 처음 n개의 자연수 제곱의 합 공식인 n(n+1)(2n+1)/6과 같습니다. 이 공식을 사용하면 루프 없이 O(1)의 시간 복잡도로 답을 구할 수 있습니다.

코드 예제

#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
    return ( n*(n + 1)*(2*n + 1) )/6;
}
int main() {
    int n = 9;
    cout<<"Sum of the series 1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+ ... + (2*"<<n<<"-1)) is "<<calcSeriesSum(n);
    return 0;
}

출력

Sum of the series 1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+ ... + (2*9-1)) is 285

정리

중첩 루프를 사용하는 방법은 구현이 간단하지만 O(n²)의 시간이 걸리는 반면, 수학적 공식을 활용하면 O(1)의 상수 시간에 결과를 얻을 수 있습니다. 따라서 실무에서는 공식 기반 접근법이 훨씬 효율적이며, 특히 n이 큰 경우에 그 차이가 두드러집니다.