C++로 매우 큰 수가 9로 나누어 떨어지는지 확인하는 방법

프로그래밍 문제나 실무에서 수십 자리, 수백 자리에 달하는 매우 큰 수가 9로 나누어 떨어지는지 확인해야 하는 경우가 있습니다. 이런 수는 int나 long long 같은 일반 정수 자료형으로 표현할 수 없기 때문에 문자열(string) 형태로 저장한 뒤 처리해야 합니다.

핵심 원리: 자릿수의 합 규칙

9의 배수 판정에는 널리 알려진 간단한 규칙이 있습니다.

어떤 수의 각 자릿수를 모두 더한 값이 9로 나누어 떨어지면, 그 수 자체도 9로 나누어 떨어집니다.

예를 들어 630720의 자릿수 합은 6 + 3 + 0 + 7 + 2 + 0 = 18이고, 18은 9로 나누어 떨어지므로 630720 역시 9의 배수입니다. 이 규칙 덕분에 실제로 거대한 수를 나눗셈할 필요 없이, 문자열을 한 번만 순회하며 자릿수의 합을 구하면 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

bool isDiv9(string num) {
    int n = num.length();
    // 각 문자의 아스키 코드 합에서 '0' * n을 빼면 실제 자릿수의 합이 됨
    long sum = accumulate(begin(num), end(num), 0) - '0' * n;
    return (sum % 9 == 0);
}

int main() {
    string num = "630720";
    if(isDiv9(num)) {
        cout << "Divisible";      // 나누어 떨어짐
    } else {
        cout << "Not Divisible";  // 나누어 떨어지지 않음
    }
}

출력 결과

Divisible

코드 동작 방식

• accumulate(begin(num), end(num), 0) : 문자열의 모든 문자를 아스키 코드 값 기준으로 합산합니다.
• '0' * n 을 빼는 이유 : 각 문자에서 문자 '0'(아스키 코드 48)만큼의 오프셋을 빼야 실제 숫자 값이 되므로, 전체 합에서 '0' × 문자열 길이를 빼주면 정확한 자릿수의 합이 계산됩니다.
• sum % 9 == 0 : 자릿수의 합이 9로 나누어 떨어지는지 검사하여 true 또는 false를 반환합니다.

시간 복잡도

문자열을 한 번만 순회하므로 시간 복잡도는 O(n)(n은 자릿수)입니다. 따라서 수천 자리에 달하는 초대형 수도 빠르게 판정할 수 있으며, 추가 메모리 사용 없이 원본 문자열만으로 처리가 가능합니다.