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

문제 개요

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

1 + (1+2) + (1+2+3) + (1+2+3+4) + … + (1+2+3+4+...+n)

예제로 이해하기

입력

n = 4

출력

설명 − (1) + (1+2) + (1+2+3) + (1+2+3+4) = 20

방법 1: 반복문을 이용한 단순 해결법

가장 직관적인 방법은 두 개의 중첩 반복문(nested loop)을 사용해 각 항을 계산하면서 누적하는 것입니다.

알고리즘

sum = 0으로 초기화
1단계: i를 1부터 n까지 반복 (i = 1 ~ n)
   1.1단계: j를 1부터 i까지 반복 (j = 1 ~ i)
      1.1.1단계: sum 값 갱신 (sum += j)
2단계: sum 반환

구현 예제

아래는 위 알고리즘의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
    int sum = 0;
    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= i ; j++)
            sum += j;
    return sum;
}
int main() {
    int n = 7;
    cout<<"수열 1 + (1+2) + (1+2+3) + (1+2+3+4) + ... + (1+2+3+4+...+"<<n<<")의 합은 "<<calcSeriesSum(n);
    return 0;
}

출력 결과

수열 1 + (1+2) + (1+2+3) + (1+2+3+4) + ... + (1+2+3+4+...+7)의 합은 84

이 방법은 이해하기 쉽지만, 중첩 반복문 때문에 시간 복잡도가 O(n²)이므로 n이 커질수록 비효율적이라는 단점이 있습니다.

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

더 효율적인 접근 방식은 수열의 일반항 공식을 유도하여 상수 시간 O(1)에 답을 계산하는 것입니다. k번째 항은 삼각수 공식 k(k+1)/2이므로, 이를 전체에 대해 합산하면 다음과 같이 정리됩니다.

공식 유도 과정

sum = 1 + (1+2) + (1+2+3) + (1+2+3+4) …
sum = Σ ( k(k+1)/2 )
sum = ½ Σ ( k² + k ) = ½ ( Σ(k²) + Σk )
sum = ½ [ (n(n+1)(2n+1))/6 + ½ · (n(n+1))/2 ]
sum = ½ [ (n(n+1))/2 · ( (2n+1)/3 + 1 ) ]
sum = ½ [ ((n(n+1))/2) × (2n + 1 + 3)/3 ]
sum = ½ [ (n(n+1)(2n+4))/6 ]
sum = (n(n+1)(2n+4))/12

따라서 최종 공식은 n(n+1)(2n+4)/12가 됩니다. 이는 사면체수(tetrahedral number) 공식 n(n+1)(n+2)/6과 동일한 형태입니다.

구현 예제

유도된 공식을 적용한 C++ 프로그램은 다음과 같습니다.

#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
    return (n*(n + 1)*(2*n + 4))/12;
}
int main() {
    int n = 7;
    cout<<"수열 1 + (1+2) + (1+2+3) + (1+2+3+4) + ... + (1+2+3+4+...+"<<n<<")의 합은 "<<calcSeriesSum(n);
}

출력 결과

수열 1 + (1+2) + (1+2+3) + (1+2+3+4) + ... + (1+2+3+4+...+7)의 합은 84

마무리

반복문을 사용하는 방법은 O(n²)의 시간 복잡도를 가지는 반면, 수학적 공식을 활용하면 O(1)의 상수 시간에 결과를 얻을 수 있습니다. 따라서 n의 값이 클수록 공식 기반 접근법이 훨씬 효율적이며, 실전 코딩 테스트에서도 권장되는 풀이 방식입니다.