C++에서 매우 큰 수가 3으로 나누어 떨어지는지 확인하는 방법

개요

프로그래밍을 하다 보면 일반적인 정수형(int, long long)으로 담을 수 없는 매우 큰 숫자가 3으로 나누어 떨어지는지 확인해야 하는 경우가 있습니다. 이런 경우에는 숫자를 문자열(string) 형태로 입력받아 처리하는 것이 효과적입니다.

3의 배수 판정 원리

3의 배수를 판별하는 가장 간단한 방법은 각 자릿수의 합을 이용하는 것입니다.

수학적으로 어떤 수의 각 자릿수를 모두 더한 값이 3으로 나누어 떨어진다면, 그 수 자체도 반드시 3으로 나누어 떨어집니다. 이 성질은 10을 3으로 나눈 나머지가 1이라는 점에서 비롯되며, 덕분에 거대한 숫자라도 자릿수의 합만 계산하면 빠르게 판정할 수 있습니다.

구현 예제 코드

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

bool isDiv3(string num){
    int n = num.length();
    // 각 문자의 ASCII 값을 모두 더한 뒤 '0' * n을 빼서 실제 자릿수 합을 구함
    long sum = accumulate(begin(num), end(num), 0) - '0' * n;
    if(sum % 3 == 0)
        return true;
    return false;
}

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

코드 설명

자릿수 합 계산

accumulate(begin(num), end(num), 0) 함수는 문자열에 포함된 모든 문자의 ASCII 코드 값을 합산합니다. 문자 '0'부터 '9'까지는 ASCII 코드상 연속된 값을 가지므로, 전체 합에서 '0' * n(n은 문자열 길이)을 빼주면 실제 각 자릿수 숫자의 합을 얻을 수 있습니다.

나눗셈 판정

계산된 자릿수 합을 3으로 나눈 나머지가 0이면 해당 수는 3의 배수입니다. 이 방식은 숫자가 아무리 커도 문자열 길이에 비례하는 선형 시간 O(n) 안에 처리할 수 있어 매우 효율적입니다.

실행 결과

Divisible

예제에서 사용한 25자리 숫자 3635883959606670431112222의 각 자릿수를 모두 더하면 3의 배수가 되므로, 프로그램은 "Divisible"(나누어 떨어짐)을 출력합니다.

마무리

이처럼 C++에서는 문자열로 표현된 임의의 크기 숫자도 자릿수 합 규칙만 활용하면 오버플로우 걱정 없이 3의 배수 여부를 손쉽게 판별할 수 있습니다. 같은 원리는 9의 배수 판정에도 그대로 적용할 수 있다는 점도 기억해 두면 유용합니다.