C++로 K^n + (K^(n-1)·(K-1)^1) + … + (K-1)^n 급수의 합 구하기

문제 개요

두 개의 정수 k와 n이 주어졌을 때, 다음과 같은 급수의 합을 구하는 프로그램을 작성해야 합니다.

Kⁿ + (K^n-1 × (K-1)¹) + (K^n-2 × (K-1)²) + … + (K-1)ⁿ

예시로 문제 이해하기

입력: n = 3, k = 4
출력: 175

설명: 급수의 각 항은 다음과 같습니다.
= 4^3 + (4^2 × 3^1) + (4^1 × 3^2) + (4^0 × 3^3)
= 64 + 48 + 36 + 27
= 175

방법 1: 반복문을 이용한 기본 풀이

가장 직관적인 방법은 for 반복문을 사용해 급수의 각 항을 하나씩 계산한 뒤, 그 값을 합계에 차례로 더하는 것입니다.

알고리즘

1. sum을 0으로 초기화한다.
2. i를 0부터 n까지 반복하면서 다음을 수행한다.
   sum += pow(k, n-i) × pow(k-1, i)
3. 반복이 끝나면 sum을 반환한다.

구현 예제

#include <iostream>
#include <math.h>
using namespace std;

int calcSeriesSum(int k, int n) {
   int sum = 0;
   for (int i = 0; i <= n; i++) {
      int p = pow(k, n-i) * pow((k-1), i);
      sum = sum + p;
   }
   return sum;
}

int main() {
   int n = 4;
   int K = 2;
   cout<<"Sum of the series is "<<calcSeriesSum(K, n);
}

실행 결과

Sum of the series is 31

이 방법은 이해하기 쉽다는 장점이 있지만, n번의 반복 연산이 필요하므로 시간 복잡도가 O(n)이 되어 큰 입력값에는 비효율적입니다.

방법 2: 등비수열 공식을 이용한 효율적인 풀이

주어진 급수를 자세히 살펴보면 등비수열임을 알 수 있습니다. 첫째 항은 kⁿ이고, 공비는 (k-1)/k입니다. 등비수열의 합 공식을 적용하면 다음과 같이 일반 공식을 유도할 수 있습니다.

sum = k^n × (1 + (k-1)/k + (k-1)²/k² + … + (k-1)^n/k^n)

등비수열의 합 공식 S = a(1 - r^(n+1)) / (1 - r)을 적용하면,

sum = k^n × (1 - ((k-1)/k)^(n+1)) / (1 - (k-1)/k)
    = k^n × ((k^(n+1) - (k-1)^(n+1)) / k^(n+1)) ÷ (1/k)
    = k^(n+1) × (k^(n+1) - (k-1)^(n+1)) / k^(n+1)
    = k^(n+1) - (k-1)^(n+1)

따라서 이 급수의 전체 합은 매우 간단한 닫힌 형태의 공식으로 표현됩니다.

sum = kⁿ⁺¹ − (k−1)ⁿ⁺¹

이 공식을 사용하면 반복 없이 단 한 번의 연산만으로 결과를 얻을 수 있어 시간 복잡도가 O(1)로 크게 향상됩니다.

구현 예제

#include <iostream>
#include <math.h>
using namespace std;

int calcSeriesSum(int k, int n) {
   return ( pow(k,(n+1)) - pow((k-1),(n+1)) );
}

int main() {
   int n = 4;
   int K = 2;
   cout<<"Sum of the series is "<<calcSeriesSum(K, n);
}

실행 결과

Sum of the series is 31

정리

K^n + (K^(n-1)·(K-1)^1) + … + (K-1)^n 형태의 급수는 k^(n+1) − (k−1)^(n+1)이라는 공식 한 줄로 계산할 수 있습니다. 반복문 기반의 O(n) 풀이보다 훨씬 빠르고 코드도 간결해지므로, 실전에서는 반복 풀이에 앞서 닫힌 형태의 공식이 존재하는지 먼저 확인해 보는 것이 좋습니다.