C++로 구현하는 큰 정수의 디지털 루트(반복 디지털 합) 계산 방법

디지털 루트란 무엇인가?

이 튜토리얼에서는 주어진 숫자의 디지털 루트(digital root)를 구하는 방법을 알아보겠습니다.

디지털 루트는 숫자의 각 자릿수를 모두 더한 후, 그 합이 한 자릿수가 될 때까지 같은 과정을 반복하여 얻는 최종 결과입니다. 예를 들어 12345라면 1+2+3+4+5 = 15이고, 다시 1+5 = 6이므로 디지털 루트는 6이 됩니다.

여기서 다루는 입력값은 문자열 형태의 정수입니다. 숫자가 매우 커서 일반적인 정수 자료형(int, long long 등)에 담을 수 없는 경우에도 처리할 수 있도록 하기 위함입니다.

핵심 아이디어: 9로 나눈 나머지 활용하기

실제로 자릿수 합을 여러 번 반복해서 계산하는 대신, 수학적 성질을 이용하면 훨씬 효율적으로 답을 구할 수 있습니다. 어떤 수와 그 수의 자릿수 합은 9로 나눈 나머지가 서로 같다는 성질이 있기 때문입니다.

따라서 디지털 루트는 다음과 같은 규칙으로 결정됩니다.

• 자릿수 합이 0이라면 답은 0입니다. (입력이 "0"인 경우)

• 자릿수 합이 9로 나누어떨어진다면 답은 9입니다.

• 그 외의 경우에는 자릿수 합을 9로 나눈 나머지가 곧 답입니다.

C++ 코드 예제

위의 접근 방식을 코드로 구현하면 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;
int digitalRoot(string n) {
    int digitsSum = 0;
    // 문자열의 각 자릿수를 숫자로 변환하여 합산
    for (int i = 0; i < n.length(); i++) {
        digitsSum += n[i] - '0';
    }
    if (digitsSum == 0) {
        return 0;
    }
    return digitsSum % 9 == 0 ? 9 : digitsSum % 9;
}
int main() {
    string n = "12345";
    cout << digitalRoot(n) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

6

12345의 자릿수 합은 1+2+3+4+5 = 15이며, 15를 9로 나누면 몫은 1이고 나머지는 6입니다. 따라서 디지털 루트인 6이 올바르게 출력되는 것을 확인할 수 있습니다.

마무리

이번 튜토리얼에서는 문자열 형태의 큰 정수에 대해 반복 계산 없이 디지털 루트를 빠르게 구하는 방법을 살펴보았습니다. 시간 복잡도는 문자열 길이에 비례하는 O(N)으로 매우 효율적입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.