주어진 숫자가 17로 나누어 떨어지는지 판별해야 하는 상황을 가정해 보겠습니다.
예를 들어 입력값이 99943이라면, 이 숫자는 17로 나누어 떨어지므로 출력 결과는 "Divisible"(나누어 떨어짐)이 됩니다.
접근 방식: 반복 뺄셈 기법
이 문제는 반복 뺄셈(repeated subtraction) 기법을 사용하면 효율적으로 해결할 수 있습니다. 원리는 다음과 같습니다.
숫자의 마지막 자릿수를 추출한 뒤, 그 값을 5배 하여 원래 숫자에서 빼는 과정을 반복합니다. 이 과정을 거치면 숫자가 점점 줄어들어 결국 두 자리 수가 되는데, 17의 배수는 이 과정을 거쳐도 여전히 17로 나누어 떨어지는 성질을 유지하기 때문에 마지막 두 자리 수만 검사하면 됩니다.
알고리즘 단계
- 숫자를 100으로 나눈 몫이 0이 아니면(즉, 세 자리 이상이면) 다음을 반복합니다.
- last_digit := 숫자를 10으로 나눈 나머지
- number := 숫자를 10으로 나눈 몫
- number := number - last_digit * 5
- 최종 숫자를 17로 나눈 나머지가 0이면 true를 반환합니다.
다음 구현 예제를 통해 더 쉽게 이해할 수 있습니다.
예제 코드
def solve(number) :
while(number // 100) :
last_digit = number % 10
number //= 10
number -= last_digit * 5
return (number % 17 == 0)
number = 99943
if solve(number) :
print("Divisible")
else :
print("Not Divisible")
입력
99943
출력
Divisible
동작 원리 살펴보기
입력값 99943에 대해 이 알고리즘이 어떻게 작동하는지 단계별로 살펴보겠습니다.
- 1단계: 마지막 자릿수는 3입니다. 숫자를 9994로 만든 후 3 × 5 = 15를 빼면 9979가 됩니다.
- 2단계: 마지막 자릿수는 9입니다. 숫자를 997로 만든 후 9 × 5 = 45를 빼면 952가 됩니다.
- 3단계: 마지막 자릿수는 2입니다. 숫자를 95로 만든 후 2 × 5 = 10을 빼면 85가 됩니다.
- 4단계: 85는 두 자리 수이므로 반복을 종료하고, 85 ÷ 17 = 5로 나누어 떨어집니다.
따라서 99943은 17의 배수임을 확인할 수 있습니다. 실제로 17 × 5879 = 99943이므로 결과가 정확함을 알 수 있습니다.
이 방법은 매 반복마다 숫자의 자릿수가 하나씩 줄어들기 때문에 시간 복잡도는 O(log n)이며, 매우 큰 숫자도 빠르게 판별할 수 있다는 장점이 있습니다.