1부터 n까지 모든 숫자의 자릿수 합 효율적으로 계산하기

문제 개요

이 문제는 1부터 n까지 범위에 있는 모든 숫자의 자릿수 합을 구하는 것입니다. 예를 들어 54의 자릿수 합은 5 + 4 = 9입니다. 이처럼 범위 내의 모든 숫자에 대해 각각 자릿수 합을 구한 뒤, 그 전체 합을 계산해야 합니다.

단순히 1부터 n까지 하나씩 확인하는 방법도 있지만, n이 매우 커지면 비효율적입니다. 다행히 자릿수가 d개인 숫자는 총 10^d-1개 존재한다는 사실을 활용하면, 재귀 공식을 통해 훨씬 빠르게 답을 구할 수 있습니다.

재귀 공식

1부터 10^d − 1까지 모든 숫자의 자릿수 합을 sum(10^d − 1)이라 하면, 다음 점화식이 성립합니다.

sum(10^d − 1) = sum(10^d-1 − 1) × 10 + 45 × 10^d-1

여기서 ×10은 기존 자릿수들이 새로운 앞자리 숫자(0~9)마다 한 번씩 반복되기 때문이고, 45 × 10^d-1는 새로 생기는 최상위 자릿수의 합(0+1+…+9 = 45)이 각각 10^d-1번 나타나기 때문입니다.

입력과 출력

입력:
알고리즘은 범위의 상한값을 입력받습니다. 예를 들어 20이 주어집니다.
출력:
1부터 n까지 모든 숫자의 자릿수 합. 이 경우 결과는 102입니다.

알고리즘

digitSumInRange(n)

입력: 범위의 상한값 n.

출력: 1부터 n까지 범위 내 모든 숫자의 자릿수 합.

Begin
    if n < 10, then
        return n(n+1)/2
    digit := n의 자릿수
    d := digit - 1
    크기가 digit인 place 배열 선언
    place[0] := 0
    place[1] := 45

    for i := 2 to d, do
        place[i] := place[i-1]*10 + 45 * ceiling(10^(i-1))
    done

    power := ceiling(10^d)
    msd := n / power
    res := msd*place[d] + (msd*(msd-1)/2)*power +
           msd*(1 + n mod power) + digitSumInRange(n mod power)
    return res
End

알고리즘 동작 원리

n이 한 자리 숫자라면 공식 n(n+1)/2로 바로 계산할 수 있습니다. 그렇지 않은 경우에는 다음 단계를 따릅니다.

최상위 자릿수(msd) 분리: n을 가장 큰 10의 거듭제곱(power)으로 나누어 최상위 자릿수와 나머지 부분으로 분리합니다.
완전한 블록의 합: msd × place[d]는 0부터 msd−1까지의 선행 자릿수를 가진 완전한 블록들의 자릿수 합입니다.
선행 자릿수의 합: (msd × (msd−1) / 2) × power는 1부터 msd−1까지의 선행 자릿수가 각각 power번 등장할 때의 합입니다.
현재 선행 자릿수의 기여: msd × (1 + n mod power)는 현재 최상위 자릿수가 나머지 구간에서 반복되는 횟수만큼 더해줍니다.
재귀 호출: 마지막으로 남은 자릿수에 대해 digitSumInRange(n mod power)를 재귀적으로 호출합니다.

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;

int digitSumInRange(int n) {
    if (n < 10)
        return n*(n+1)/2;          // 한 자리 숫자면 공식으로 바로 계산
    int digit = log10(n)+1;        // 숫자의 자릿수
    int d = digit-1;               // 자릿수에서 1 감소

    int *place = new int[d+1];     // 1부터 10^i - 1까지의 자릿수 합을 저장하는 배열
    place[0] = 0;
    place[1] = 45;

    for (int i=2; i<=d; i++)
        place[i] = place[i-1]*10 + 45*ceil(pow(10,i-1));

    int power = ceil(pow(10, d));  // 10의 거듭제곱 계산
    int msd = n/power;             // 최상위 자릿수(msd) 추출
    return msd*place[d] + (msd*(msd-1)/2)*power +
        msd*(1+n%power) + digitSumInRange(n%power);  // 재귀적으로 합 계산
}

int main() {
    int n;
    cout << "범위의 상한값을 입력하세요: ";
    cin >> n;
    cout << "1부터 " << n << "까지의 자릿수 합: " << digitSumInRange(n);
}

실행 결과

범위의 상한값을 입력하세요: 20
1부터 20까지의 자릿수 합: 102

마무리

이 알고리즘은 재귀 호출이 진행될 때마다 처리해야 할 자릿수가 하나씩 줄어들기 때문에, 1부터 n까지 일일이 더하는 방식보다 훨씬 효율적입니다. n이 아무리 커도 자릿수에 비례하는 적은 연산 횟수만으로 답을 구할 수 있어, 매우 큰 입력값에도 빠르게 동작합니다.