C++로 1 + 22 + 333 + 4444 + … 수열의 n항까지의 합 구하기

이 문제에서는 정수 N이 주어지며, 우리의 목표는 1 + 22 + 333 + 4444 + 55555… 형태로 이루어진 수열의 n항까지의 합을 구하는 것입니다.

문제 이해하기

예제를 통해 문제를 살펴보겠습니다.

입력 : N = 4
출력 : 4800

설명 −

1 + 22 + 333 + 4444 = 4800

이 수열의 규칙은 간단합니다. k번째 항은 숫자 k가 k번 반복된 값입니다. 즉, 3번째 항은 333, 4번째 항은 4444, 5번째 항은 55555가 됩니다.

해결 접근 방식

이 문제를 효율적으로 푸는 방법은 수열의 일반항을 구한 뒤, n항까지의 합을 하나의 닫힌 형태(closed form) 공식으로 정리하는 것입니다. 공식을 사용하면 반복문 없이 단 한 번의 계산으로 답을 얻을 수 있으므로 시간 복잡도를 O(1) 수준까지 줄일 수 있습니다.

대상 수열은 다음과 같습니다.

1 + 22 + 333 + 4444 + 55555…

k번째 항은 숫자 k가 k번 반복된 값이므로 다음과 같이 표현할 수 있습니다.

k번째 항 = k × (10^k − 1) / 9

여기서 (10^k − 1)/9는 1, 11, 111처럼 1이 k개 나열된 수(레퓨닛, repunit)를 의미합니다. 따라서 전체 합은 다음과 같이 쓸 수 있습니다.

Sum = 1×(10¹−1)/9 + 2×(10²−1)/9 + 3×(10³−1)/9 + … + n×(10ⁿ−1)/9

1/9를 공통으로 묶으면,

Sum = (1/9) × { (1×10¹ + 2×10² + 3×10³ + … + n×10ⁿ) − (1 + 2 + 3 + … + n) }

등차수열의 합 공식 (1 + 2 + … + n) = n(n+1)/2를 적용하면,

Sum = (1/9) × { (1×10¹ + 2×10² + … + n×10ⁿ) − n(n+1)/2 }

남은 문제는 첫 번째 괄호 안의 합 S = Σ k·x^k를 구하는 것입니다. 이는 기본 등비수열 공식

1 + x + x² + x³ + … + xⁿ = (xⁿ⁺¹ − 1)/(x − 1)

의 양변을 x에 대해 미분한 후 x = 10을 대입하면 구할 수 있으며, 그 결과는 다음과 같습니다.

S = { n×10ⁿ⁺² − (n+1)×10ⁿ⁺¹ + 10 } / 81

이 값을 원래 식에 다시 대입하고 분모를 통일해 정리하면,

Sum = (1/1458) × { 2×(n×10ⁿ⁺² − (n+1)×10ⁿ⁺¹ + 10) − 81×n×(n+1) }

= (1/1458) × { 10ⁿ⁺¹×(20n − 2n − 2) − 81n² − 81n + 20 }

= (1/1458) × { 10ⁿ⁺¹×(18n − 2) − 81n² − 81n + 20 }

이것이 최종 공식입니다. n값만 대입하면 반복 계산 없이 즉시 합을 구할 수 있습니다.

C++ 구현 예제

위에서 유도한 공식을 활용한 솔루션의 동작을 보여주는 프로그램입니다.

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

int calcSumNTerms(int n) {
   return ( ( (18*n - 2)*(pow(10, n+1)) - 81*n*n - 81*n + 20 )/1458 );
}

int main() {
   int n = 5;
   cout<<"The sum of series upto n terms is "<<calcSumNTerms(n);
   return 0;
}

출력 결과

The sum of series upto n terms is 60355

검산해 보면 1 + 22 + 333 + 4444 + 55555 = 60355로, 공식으로 얻은 결과와 정확히 일치합니다.

복잡도 분석

시간 복잡도: O(1) — 산술 연산 관점에서 상수 시간이며, pow() 함수의 거듭제곱 계산까지 고려해도 O(log n) 수준입니다. 반복문으로 각 항을 생성하는 풀이(O(n²))보다 훨씬 빠릅니다.

공간 복잡도: O(1) — 추가 메모리를 거의 사용하지 않습니다.

참고: 10의 거듭제곱은 매우 빠르게 커지므로 n이 조금만 커져도 int 범위를 초과하게 됩니다. 실무에서는 long long 타입을 사용하거나, 더 큰 n에 대해서는 임의 정밀도 정수(C++의 boost::multiprecision::cpp_int, Java의 BigInteger, Python의 int 등)를 활용하는 것이 안전합니다.