C++로 구하는 홀수 제곱 수열의 합: 1² + 3² + 5² + … + (2n−1)²

문제 개요

자연수 n이 주어졌을 때, 홀수들의 제곱으로 이루어진 수열 1² + 3² + 5² + … + (2n−1)²의 합을 구하는 문제입니다. i번째 홀수는 2i−1로 표현할 수 있으므로, 이 값들을 n개 만큼 모두 더하면 전체 합이 됩니다.

예시

입력:

n = 5

출력:

165

설명:

합 = 1² + 3² + 5² + 7² + 9²
   = 1 + 9 + 25 + 49 + 81
   = 165

방법 1: 반복문으로 직접 계산하기

가장 직관적인 접근 방식은 반복문을 사용해 각 항을 하나씩 더하는 것입니다. 변수 i를 1부터 n까지 순회하면서 (2i−1)² 값을 누적 변수에 더해주면 됩니다. 이 방법의 시간 복잡도는 O(n)입니다.

#include <iostream>
using namespace std;

int calcSumOfSeries(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += (2 * i - 1) * (2 * i - 1);
    return sum;
}

int main() {
    int n = 5;
    cout << "The sum of series up to " << n << " is " << calcSumOfSeries(n);
    return 0;
}

출력:

The sum of series up to 5 is 165

방법 2: 수학 공식 활용하기

반복문 없이 수학 공식을 사용하면 단 한 번의 연산으로 결과를 얻을 수 있어 훨씬 효율적입니다. 홀수 제곱의 합은 다음과 같이 유도할 수 있습니다.

Σ(2i−1)² = Σ(4i² − 4i + 1)
         = 4·Σi² − 4·Σi + n
         = n(2n − 1)(2n + 1) / 3

따라서 수열의 합은 아래 공식으로 바로 계산할 수 있습니다.

합 = n × (2n − 1) × (2n + 1) / 3

이 방식은 n의 크기와 무관하게 상수 시간 O(1) 안에 답을 구합니다.

#include <iostream>
using namespace std;

int calcSumOfSeries(int n) {
    return (n * (2 * n - 1) * (2 * n + 1)) / 3;
}

int main() {
    int n = 5;
    cout << "The sum of series up to " << n << " is " << calcSumOfSeries(n);
    return 0;
}

출력:

The sum of series up to 5 is 165

마무리

n이 작다면 반복문 방식으로도 충분하지만, n이 매우 큰 경우에는 O(1) 공식 기반 풀이가 압도적으로 빠릅니다. 다만 n이 커지면 곱셈 결과가 int 범위를 넘을 수 있으므로, 필요하다면 long long 타입을 사용해 오버플로우를 방지하는 것이 좋습니다.