C++에서 매우 큰 숫자가 11로 나누어 떨어지는지 확인하는 방법

프로그래밍 문제를 풀다 보면 int나 long long 같은 일반적인 정수 자료형으로는 담을 수 없을 만큼 큰 숫자를 다뤄야 할 때가 있습니다. 이 글에서는 문자열 형태로 주어진 매우 큰 숫자가 11로 나누어 떨어지는지 확인하는 방법을 살펴봅니다.

11의 배수 판별법

11의 배수를 판별하는 대표적인 방법은 자릿수를 교대로 묶어 비교하는 것입니다. 숫자의 자릿값을 왼쪽부터 홀수 번째 자리와 짝수 번째 자리로 나눈 뒤, 각 그룹의 자릿수 합을 각각 구합니다. 두 합의 차이가 0 또는 11의 배수라면 그 숫자는 11로 나누어 떨어집니다.

특히 두 합이 정확히 같다면(차이가 0이라면) 반드시 11의 배수이므로, 아래 예제 코드에서는 이 경우를 검사합니다.

예제 코드

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

// 문자열로 표현된 숫자가 11로 나누어 떨어지는지 확인하는 함수
bool isDiv11(string num){
    int n = num.length();
    long odd_sum = 0, even_sum = 0;
    for(int i = 0; i < n; i++){
        if(i % 2 == 0){          // 짝수 인덱스(홀수 번째 자리)
            odd_sum += num[i] - '0';
        } else {                 // 홀수 인덱스(짝수 번째 자리)
            even_sum += num[i] - '0';
        }
    }
    return (odd_sum == even_sum);
}

int main() {
    string num = "1234567589333892";   // 매우 큰 숫자를 문자열로 저장
    if(isDiv11(num)){
        cout << "Divisible";           // 나누어 떨어짐
    } else {
        cout << "Not Divisible";       // 나누어 떨어지지 않음
    }
}

실행 결과

Divisible

코드 동작 원리

• 문자열 처리: 숫자가 너무 커서 정수형 변수에 저장할 수 없으므로, 각 자릿수를 문자열의 문자 하나하나로 다룹니다.
• 자릿수 변환: num[i] - '0' 연산으로 문자를 실제 숫자 값으로 바꿉니다. 예를 들어 문자 '7'의 ASCII 코드는 55, '0'은 48이므로 55 - 48 = 7이 됩니다.
• 교대 합 계산: 인덱스가 짝수인 자리의 숫자는 odd_sum에, 홀수인 자리의 숫자는 even_sum에 더해 두 그룹의 합을 각각 누적합니다.
• 판별: 두 합이 같으면 참(true)을 반환하여 11로 나누어 떨어짐을 알립니다.

예제 입력 "1234567589333892"의 경우 교대로 묶인 두 그룹의 자릿수 합이 모두 39로 같기 때문에 "Divisible"이 출력됩니다. 실제로 1234567589333892 ÷ 11 = 112233417212172로 나누어떨어짐을 확인할 수 있습니다.

시간 복잡도

이 알고리즘은 문자열의 각 문자를 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다(n은 숫자의 자릿수). 따라서 자릿수가 수천, 수만 개에 달하는 초대형 숫자도 효율적으로 판별할 수 있습니다.

참고 사항

완전한 11의 배수 판별법에서는 두 합의 차이가 11의 배수(예: 11, 22, 33…)인 경우도 포함됩니다. 위 코드는 차이가 0인 경우만 검사하므로, 모든 경우를 처리하려면 조건을 (odd_sum - even_sum) % 11 == 0으로 확장하면 됩니다.