Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 급수의 합 구하기: 1×2×3 + 2×3×4 + 3×4×5 + ... + n(n+1)(n+2)

이 문제에서는 급수의 마지막 항을 결정하는 숫자 n이 주어집니다. 우리의 목표는 C++로 급수 1×2×3 + 2×3×4 + 3×4×5 + ... + n(n+1)(n+2)의 합을 구하는 프로그램을 작성하는 것입니다.

문제 설명

주어진 급수는 각 항이 연속된 세 개의 자연수 곱으로 이루어져 있습니다. 즉, k번째 항은 k×(k+1)×(k+2)이며, 첫 번째 항부터 n번째 항까지의 전체 합을 계산해야 합니다. 이를 수식으로 표현하면 Σ k(k+1)(k+2) (k=1부터 n까지)의 형태가 됩니다.

예시로 이해하기

입력:

n = 5

출력:

420

설명:

1×2×3 + 2×3×4 + 3×4×5 + 4×5×6 + 5×6×7 = 6 + 24 + 60 + 120 + 210 = 420

해결 방법 1: 반복문 활용

가장 직관적인 방법은 1부터 n까지 반복문을 돌면서 각 항의 곱을 계산하고 누적 변수에 더하는 것입니다. 반복문이 종료되면 누적된 값을 반환하면 됩니다.

알고리즘

  • 1단계 - i를 1부터 n까지 반복합니다.
    • 1.1단계 - sumVar에 i×(i+1)×(i+2)를 더해 갱신합니다.
  • 2단계 - sumVar를 출력합니다.

구현 예제

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
    int sumVar = 0;
    for(int i = 1; i <= n; i++)
        sumVar = sumVar + ( (i)*(i+1)*(i+2) );
    return sumVar;
}
int main(){
    int n = 7;
    cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
    return 0;
}

출력 결과

The sum of series till 7 is 1260

이 방법은 이해하기 쉽지만, n번의 반복 연산이 필요하므로 시간 복잡도가 O(N)입니다. n이 매우 커지면 성능이 떨어질 수 있다는 단점이 있습니다.

해결 방법 2: 수학 공식 활용

더 효율적인 접근법은 급수의 합에 대한 닫힌 형태(closed-form) 공식을 유도하는 것입니다. 앞서 살펴본 것처럼 이 급수는 Σ k(k+1)(k+2)로 표현할 수 있습니다.

공식 유도 과정

먼저 일반항을 전개합니다.

k(k+1)(k+2) = (k²+k)(k+2) = k³ + 3k² + 2k

따라서 급수의 합은 다음과 같이 분해됩니다.

Sum = Σk³ + 3Σk² + 2Σk   (각 합은 k=1부터 n까지)

여기에 잘 알려진 거듭제곱 합 공식을 적용합니다.

  • Σk³ = [n(n+1)/2]²
  • Σk² = n(n+1)(2n+1)/6
  • Σk = n(n+1)/2

이 공식들을 대입한 뒤 공통 인수를 묶어 정리하면,

Sum = [n(n+1)]²/4 + n(n+1)(2n+1)/2 + n(n+1)
    = [n(n+1)/4] × [n(n+1) + 2(2n+1) + 4]
    = [n(n+1)/4] × [n² + 5n + 6]
    = [n(n+1)/4] × [(n+2)(n+3)]
    = n(n+1)(n+2)(n+3) / 4

즉, n번째 항까지의 급수 합은 다음 공식 하나로 즉시 계산할 수 있습니다.

Sum = n(n+1)(n+2)(n+3) / 4

구현 예제

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
    int sumVar = 0;
    sumVar = ( (n)*(n + 1)*(n + 2)*(n + 3)/4 );
    return sumVar;
}
int main(){
    int n = 7;
    cout<<"The sum of series till "<<n<<" is "<<calcSeriesSum(n);
    return 0;
}

출력 결과

The sum of series till 7 is 1260

마무리

두 가지 방법 모두 동일한 결과를 제공하지만, 수학 공식을 활용한 두 번째 방법은 반복문 없이 O(1)의 상수 시간에 결과를 얻을 수 있어 훨씬 효율적입니다. 검증해 보면 n=5일 때 5×6×7×8/4 = 420, n=7일 때 7×8×9×10/4 = 1260으로 반복문 방식의 결과와 정확히 일치합니다. 입력 크기가 큰 경우에는 반드시 공식 기반 접근법을 사용하는 것이 좋습니다.