C++에서 매우 큰 숫자가 20으로 나누어 떨어지는지 확인하기
이번 글에서는 주어진 숫자가 20으로 나누어 떨어지는지 판별하는 방법을 살펴보겠습니다. 이 문제에서 다루는 숫자는 매우 클 수 있기 때문에 일반적인 정수형(int, long long 등)에 담을 수 없으며, 문자열(string) 형태로 입력받아 처리해야 합니다.
핵심 아이디어
어떤 수가 20으로 나누어 떨어지려면 다음 두 가지 조건을 모두 만족해야 합니다.
- 10으로 나누어 떨어져야 합니다. 즉, 일의 자리 숫자가 반드시 '0'이어야 합니다.
- 10으로 나눈 몫이 2로 나누어 떨어져야 합니다. 이는 곧 십의 자리(끝에서 두 번째 자릿수)가 짝수라는 의미입니다.
두 조건이 동시에 충족되면 그 수는 20의 배수입니다. 따라서 문자열 전체를 검사할 필요 없이 마지막 두 자릿수만 확인하면 되므로 아주 간단하게 해결할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
bool isDiv20(string num){
int n = num.length();
if(num[n - 1] != '0')
return false;
int second_last = num[n - 2] - '0';
if(second_last % 2 == 0)
return true;
return false;
}
int main() {
string num = "54871584540";
if(isDiv20(num)){
cout << "Divisible";
}else{
cout << "Not Divisible";
}
}
코드 설명
isDiv20 함수는 먼저 문자열의 마지막 문자가 '0'인지 검사하여 10의 배수 여부를 확인합니다. 만약 아니라면 즉시 false를 반환합니다. 그다음 끝에서 두 번째 문자를 정수로 변환한 뒤(- '0' 연산 활용), 그 값이 짝수인지 확인합니다. 두 조건을 모두 통과하면 true를 반환합니다.
출력 결과
Divisible
입력으로 사용된 "54871584540"은 마지막 자릿수가 0이고, 십의 자리 숫자가 4(짝수)이므로 20으로 나누어 떨어집니다. 실제로 54871584540 ÷ 20 = 2743579227로 나눗셈이 성립합니다.
복잡도 분석
- 시간 복잡도: O(1) — 문자열 길이와 관계없이 마지막 두 문자만 검사합니다.
- 공간 복잡도: O(1) — 추가 메모리를 거의 사용하지 않습니다.