C++로 주어진 수열의 합을 구하는 프로그램

이 문제에서는 두 개의 정수 n과 k가 주어지며, C++로 해당 수열의 합을 구하는 프로그램을 작성하는 것이 목표입니다.

수열은 다음과 같습니다.

(1×2×3×…×k) + (2×3×4×…×(k+1)) + (3×4×5×…×(k+2)) + … + ((n−k+1)×(n−k+2)×…×n)

문제 설명 − 주어진 k값을 기준으로 n번째 항까지 수열의 각 항을 계산하고, 그 합을 구합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력

n = 4, k = 3

출력

30

설명

수열: (1×2×3) + (2×3×4) = 6 + 24 = 30

풀이 접근 방식

가장 간단한 방법은 반복문을 사용해 합을 구하는 것입니다. 바깥쪽 루프는 각 항을 차례로 처리하고, 안쪽 루프는 해당 항의 값을(연속된 숫자의 곱) 계산합니다. 이후 각 항의 값을 모두 더하면 최종 결과를 얻을 수 있습니다.

구현 코드

#include <iostream>
using namespace std;

int findSeriesSum(int n, int k){
    int sumVal = 0, term = 1;
    for(int i = 1; i <= (n - k + 1); i++){
        term = 1;
        for(int j = i; j < (i + k); j++){
            term *= j;
        }
        sumVal += term;
    }
    return sumVal;
}

int main(){
    int n = 4, k = 3;
    cout << "The sum of series is " << findSeriesSum(n, k);
    return 0;
}

출력

The sum of series is 30

이 방법은 중첩 루프를 사용하기 때문에 시간 복잡도가 O(n²) 수준이 되어 입력 크기가 커질수록 비효율적이라는 단점이 있습니다.

효율적인 풀이는 수열의 일반 공식을 활용하는 것입니다. 이 수열의 합은 다음 공식으로 한 번에 계산할 수 있습니다.

((n+1) × n × (n−1) × (n−2) × … × (n−k+1)) / (k+1)

공식을 사용하면 단 하나의 루프만으로 결과를 구할 수 있으므로 실행 시간을 크게 줄일 수 있습니다.

구현 코드

#include <iostream>
using namespace std;

int findSeriesSum(int n, int k){
    int sumVal = 1;
    for(int i = n + 1; i > n - k; i--)
        sumVal *= i;
    sumVal /= (k + 1);
    return sumVal;
}

int main(){
    int n = 4, k = 3;
    cout << "The sum of series is " << findSeriesSum(n, k);
    return 0;
}

출력

The sum of series is 30