프로그래밍 문제를 풀다 보면 일반적인 정수 자료형 범위를 훌쩍 넘는 매우 큰 숫자가 75로 나누어떨어지는지 확인해야 하는 경우가 있습니다. 이런 경우 숫자를 문자열(string) 형태로 처리하면 손쉽게 판별할 수 있습니다.
75의 배수 판정 원리
75는 3과 25의 곱(75 = 3 × 25)으로 표현할 수 있으므로, 어떤 수가 3으로도 나누어떨어지고 25로도 나누어떨어진다면 그 수는 반드시 75로 나누어떨어집니다. 각 조건은 다음과 같은 간단한 규칙으로 판별할 수 있습니다.
- 3의 배수 판정: 모든 자릿수의 합이 3으로 나누어떨어지면, 그 수는 3의 배수입니다.
- 25의 배수 판정: 마지막 두 자릿수가 25로 나누어떨어지면(즉, 끝이 00, 25, 50, 75이면), 그 수는 25의 배수입니다.
C++ 구현 예제
아래 코드는 숫자를 문자열로 입력받아 위 두 조건을 검사한 후, 75의 배수 여부를 판별합니다.
#include <bits/stdc++.h>
using namespace std;
bool isDiv75(string num){
int n = num.length();
// 각 자릿수의 합 계산
long sum = accumulate(begin(num), end(num), 0) - '0' * n;
if(sum % 3 != 0)
return false;
// 마지막 두 자릿수를 정수로 변환
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 = "1754586672150";
if(isDiv75(num)){
cout << "Divisible";
}else{
cout << "Not Divisible";
}
}
코드 동작 설명
accumulate함수를 사용해 문자열 내 모든 문자의 ASCII 값 합을 구한 뒤,'0' * n을 빼서 실제 자릿수의 합을 계산합니다.- 자릿수의 합이 3으로 나누어떨어지지 않으면 즉시
false를 반환하고 종료합니다. - 마지막 두 문자를 숫자로 변환해 두 자릿수 값을 만들고, 이 값이 25로 나누어떨어지는지 검사합니다.
- 두 조건을 모두 통과하면
true, 하나라도 실패하면false를 반환합니다.
이 알고리즘은 문자열 길이에 비례하는 O(n) 시간 복잡도로 동작하기 때문에, 숫자가 아무리 커도 빠르게 판별할 수 있다는 장점이 있습니다. 단, 마지막 두 자릿수를 검사해야 하므로 입력 숫자는 최소 두 자릿수 이상이어야 합니다.
출력 결과
Divisible
예제에서 사용한 수 1754586672150의 자릿수 합은 57로 3으로 나누어떨어지고, 마지막 두 자릿수인 50 역시 25로 나누어떨어지므로, 이 수는 75의 배수임을 알 수 있습니다.