Python으로 큰 숫자가 19로 나누어 떨어지는지 확인하는 방법

아주 큰 숫자가 주어졌을 때, 해당 숫자가 19로 나누어 떨어지는지 확인해야 하는 경우가 있습니다.

예를 들어 입력값이 86982라면, 결과는 "Divisible"(나누어 떨어짐)이 됩니다.

해결 접근 방법

이 문제는 반복 덧셈(repeated addition) 기법을 사용하여 효율적으로 해결할 수 있습니다. 이 방법의 핵심 아이디어는 다음과 같습니다.

• 숫자에서 마지막 자릿수를 분리합니다.
• 분리한 자릿수에 2를 곱합니다.
• 그 값을 나머지 숫자에 더합니다.
• 숫자가 두 자리 수가 될 때까지 위 과정을 반복합니다.
• 최종 숫자가 19로 나누어 떨어지면, 원래 숫자도 19로 나누어 떨어집니다.

이는 19의 배수 판정법 중 하나로, 아주 큰 숫자를 작은 숫자로 단계적으로 줄여가며 손쉽게 검사할 수 있다는 장점이 있습니다.

알고리즘 단계

이 문제를 해결하기 위해 다음 단계를 따릅니다.

• 숫자가 100 이상인 동안 다음 과정을 반복합니다.
  • last_digit := number mod 10 (마지막 자릿수 추출)
  • number := number ÷ 10의 몫 (마지막 자릿수 제거)
  • number := number + last_digit × 2
• number mod 19가 0이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

구현 예제

다음 구현을 통해 더 잘 이해해 보겠습니다.

def solve(number) :
    while(number // 100) :
        last_digit = number % 10
        number //= 10
        number += last_digit * 2
    return (number % 19 == 0)
number = 86982
if solve(number) :
    print("Divisible")
else :
    print("Not Divisible")

입력

86982

출력

Divisible

동작 과정 살펴보기

입력값 86982에 대해 알고리즘이 어떻게 동작하는지 단계별로 확인해 보겠습니다.

• 86982 → 마지막 자릿수 2를 분리 후, 8698 + 2×2 = 8702
• 8702 → 마지막 자릿수 2를 분리 후, 870 + 2×2 = 874
• 874 → 마지막 자릿수 4를 분리 후, 87 + 4×2 = 95

최종적으로 얻은 95는 19의 배수(19 × 5 = 95)이므로, 원래 숫자인 86982 역시 19로 나누어 떨어진다는 것을 확인할 수 있습니다.