C++로 처음 n개의 자연수의 합(이중 합) 구하기

문제 개요

이 문제는 처음 n개의 자연수에 대한 '합의 합'을 구하는 것입니다. 즉, 1부터 n까지 각 숫자 k에 대해 '1부터 k까지의 합'을 차례대로 계산한 뒤, 이 값들을 모두 더해 최종 결과를 얻습니다.

예를 들어 입력값이 4일 때의 동작 과정은 다음과 같습니다.

입력 : 4
출력 : 20
설명 :
처음 1개 자연수의 합 = 1
처음 2개 자연수의 합 = 1 + 2 = 3
처음 3개 자연수의 합 = 1 + 2 + 3 = 6
처음 4개 자연수의 합 = 1 + 2 + 3 + 4 = 10
합의 합 = 1 + 3 + 6 + 10 = 20

접근 방법

처음 k개의 자연수의 합은 잘 알려진 공식 k × (k + 1) / 2로 한 번에 구할 수 있습니다. 따라서 1부터 n까지 반복하면서 각 단계의 합을 공식으로 계산하고, 이를 누적하면 전체 답을 효율적으로 구할 수 있습니다.

수식으로 표현하면 다음과 같습니다.

결과 = Σ (i × (i + 1) / 2), 단 i는 1부터 n까지

C++ 구현 예제

#include <iostream>
using namespace std;

int sumofSum(int n){
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += i * (i + 1) / 2; // 처음 i개 자연수의 합을 누적
    return sum;
}

int main(){
    int n = 4;
    cout << "처음 " << n << "개 자연수의 합의 합은 " << sumofSum(n);
    return 0;
}

실행 결과

처음 4개 자연수의 합의 합은 20

시간 복잡도

위 코드는 1부터 n까지 한 번씩만 순회하므로 시간 복잡도는 O(n)입니다. 참고로 수학적으로는 Σ i(i+1)/2 = n(n+1)(n+2)/6이라는 닫힌 형태(closed form)가 존재하기 때문에, 이 공식을 사용하면 O(1)에도 계산할 수 있습니다.