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

이 글에서는 주어진 수가 25로 나누어 떨어지는지 확인하는 방법을 알아보겠습니다. 여기서 다루는 수는 일반적인 정수 자료형으로 표현할 수 없을 만큼 매우 큰 수이기 때문에, 숫자를 문자열(string) 형태로 입력받아 처리합니다.

25의 배수 판별 원리

어떤 수가 25로 나누어 떨어지려면 다음 조건 중 하나를 만족해야 합니다.

• 마지막 두 자리가 00인 경우
• 마지막 두 자리로 만든 수가 25로 나누어 떨어지는 경우 (즉, 00, 25, 50, 75)

이는 100이 25의 배수이므로, 100 이상의 자릿수는 판별에 영향을 주지 않고 마지막 두 자리만 확인하면 되기 때문입니다. 예를 들어 451851549333150의 마지막 두 자리는 '50'이고, 50은 25로 나누어 떨어지므로 전체 수도 25의 배수입니다.

C++ 구현 예제

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

bool isDiv25(string num){
    int n = num.length();
    // 마지막 두 자리를 정수 값으로 변환
    int last_two_digit_val = (num[n-2] - '0') * 10 + (num[n-1] - '0');
    if(last_two_digit_val % 25 == 0)
        return true;
    return false;
}

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

실행 결과

Divisible

코드 설명

문자열의 각 문자는 문자 코드 형태로 저장되므로, '0'을 빼주면 해당 숫자의 실제 정숫값을 얻을 수 있습니다. 십의 자리 문자에 10을 곱하고 일의 자리 값을 더하면 마지막 두 자리를 하나의 정수로 만들 수 있습니다. 이 값이 25로 나누어 떨어지면 전체 수 역시 25의 배수입니다.

주의 사항

위 구현은 입력 문자열의 길이가 최소 2자리 이상이라고 가정합니다. 한 자리 숫자(예: "7")를 처리해야 한다면, 길이가 1인 경우 별도로 처리하거나 앞에 '0'을 붙여 두 자리로 맞춘 후 검사하는 것이 안전합니다.

시간 복잡도

이 방법은 문자열의 길이와 무관하게 마지막 두 문자만 확인하므로 O(1)의 시간 복잡도를 가집니다. 아무리 큰 수라도 즉시 판별할 수 있다는 점이 이 기법의 가장 큰 장점입니다.