매우 큰 숫자가 13으로 나누어 떨어지는지 확인해야 하는 경우가 종종 있습니다. 이런 숫자는 int나 long long 같은 일반적인 정수 자료형에 담을 수 없기 때문에, 문자열(string) 형태로 입력받아 처리해야 합니다.
숫자가 13으로 나누어 떨어지는지 판별하는 대표적인 방법은 다음 두 가지입니다.
- 교대 합(Alternating Sum) 방식 : 숫자를 오른쪽에서 왼쪽으로 세 자리씩 묶은 블록들을 번갈아 더하고 빼는 교대 합이 13으로 나누어 떨어지면, 원래 숫자도 13으로 나누어 떨어집니다. 예를 들어 2911285의 교대 합은 2 − 911 + 285 = −650이고, −650은 13으로 나누어 떨어지므로 2911285 역시 13으로 나누어 떨어집니다.
- 마지막 자릿수 활용 방식 : 마지막 자릿수에 4를 곱한 값을 나머지 앞자리 숫자에 더해 만든 새로운 수가 13으로 나누어 떨어지면, 원래 숫자도 13으로 나누어 떨어집니다. 예를 들어 2353에 이 규칙을 적용하면 235 + 3 × 4 = 247이 되고, 여기에 한 번 더 적용하면 24 + 7 × 4 = 52가 됩니다. 52는 13으로 나누어 떨어지므로 2353도 13으로 나누어 떨어집니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
bool isDiv13(string num){
int length = num.size();
if (length == 1 && num[0] == '0')
return true;
if (length % 3 == 1) { // 길이가 3으로 나누어 떨어지지 않고 나머지가 1인 경우
num += "00";
length += 2;
} else if (length % 3 == 2) { // 길이가 3으로 나누어 떨어지지 않고 나머지가 2인 경우
num += "0";
length += 1;
}
int sum = 0, p = 1;
for (int i = length - 1; i >= 0; i--) {
int set = 0;
set += (num[i--] - '0');
set += (num[i--] - '0') * 10;
set += (num[i] - '0') * 100;
sum = sum + set * p;
p *= (-1);
}
sum = abs(sum);
return (sum % 13 == 0);
}
int main() {
string num = "83959092724";
if(isDiv13(num)){
cout << "Divisible";
} else {
cout << "Not Divisible";
}
}
코드 동작 원리
isDiv13 함수는 문자열 형태의 숫자를 받아 13으로 나누어 떨어지는지 여부를 반환합니다. 먼저 숫자의 길이가 3의 배수가 아니면 오른쪽 끝에 '0'을 덧붙여 길이를 3의 배수로 맞춥니다. 이후 오른쪽부터 세 자리씩 잘라 하나의 세 자리 수(블록)로 만들고, 각 블록에 교대로 +1과 −1 부호를 곱해 모두 더합니다. 마지막으로 합의 절댓값이 13으로 나누어 떨어지는지 검사해 결과를 반환합니다.
예를 들어 83959092724는 자릿수가 11이므로 끝에 0을 붙여 839590927240으로 만든 뒤, 블록별 교대 합을 계산하면 240 − 927 + 590 − 839 = −936이 됩니다. 936은 13 × 72이므로 이 숫자는 13으로 나누어 떨어집니다.
출력 결과
Divisible
입력된 숫자 83959092724는 13으로 나누어 떨어지므로 Divisible이 출력됩니다.