파이썬으로 0과 9만 사용해 n의 가장 작은 배수 찾기

숫자 n이 주어졌을 때, 0과 9 두 숫자로만 구성되면서 n의 배수가 되는 가장 작은 양의 정수 x를 찾는 것이 이번 글의 목표입니다.

예를 들어 n = 26이 주어지면 정답은 90090입니다. 90090은 0과 9로만 이루어져 있으며, 26 × 3465 = 90090이므로 26의 배수이기 때문입니다.

핵심 아이디어: 이진수 활용하기

0과 9로 이루어진 수를 일일이 만들어 검사하는 것은 비효율적입니다. 대신 이진수(binary)의 성질을 활용하면 깔끔하게 해결할 수 있습니다.

모든 이진수는 0과 1로만 구성됩니다. 여기서 이진 표현의 1을 모두 9로 바꾸면, 자동으로 0과 9로만 이루어진 십진수를 얻게 됩니다. 또한 x를 1부터 차례대로 늘려가며 검사하면 자릿수가 짧은 수, 즉 값이 작은 수부터 순서대로 확인하게 되므로, 처음으로 조건을 만족하는 값이 곧 최솟값이 됩니다.

알고리즘 단계

• m을 9로, x를 1로 초기화합니다.
• m이 n으로 나누어 떨어지지 않는 동안 다음을 반복합니다.
  • x를 1 증가시킵니다.
  • x의 이진 표현에서 모든 '1'을 '9'로 바꾼 값을 새로운 m으로 설정합니다.
• 반복이 끝나면 m을 정수로 반환합니다.

파이썬 구현

def solve(n):
    m = 9
    x = 1
    while m % n != 0:
        x += 1
        m = int(bin(x)[2:].replace('1', '9'))
    return m

n = 26
print(solve(n))

코드를 살펴보면, bin(x)는 x의 이진 문자열(예: '0b10010')을 반환하고, [2:]로 앞의 '0b' 접두사를 제거합니다. 이후 replace('1', '9')로 1을 모두 9로 바꾸고, 마지막에 int()로 정수형으로 변환합니다.

실행 결과

입력:

26

출력:

90090

동작 과정 살펴보기

n = 26일 때 내부적으로 검사되는 후보 값들은 다음과 같습니다.

• x = 1 → 이진수 '1' → 9 (26의 배수 아님)
• x = 2 → 이진수 '10' → 90 (26의 배수 아님)
• x = 3 → 이진수 '11' → 99 (26의 배수 아님)
• ...
• x = 18 → 이진수 '10010' → 90090 (26의 배수! 반환)

이처럼 후보가 값이 작은 순서대로 생성되기 때문에, 처음 발견된 배수가 곧 최소값임을 보장할 수 있습니다.

다른 예시

n = 7을 입력하면 9009가 출력됩니다. 9009 = 7 × 1287이며, 0과 9로만 이루어진 7의 배수 중 가장 작은 값입니다.

복잡도 및 참고 사항

자릿수가 d인 0/9 숫자의 개수는 최대 2^d개이므로, 답의 자릿수가 커지면 반복 횟수도 기하급수적으로 늘어날 수 있습니다. 그럼에도 불구하고 아이디어가 직관적이고 구현이 매우 간단하여, 코딩 테스트나 알고리즘 학습에서 유용하게 쓰이는 패턴입니다.

참고로 임의의 n에 대해서도 이러한 조건을 만족하는 배수는 항상 존재합니다. 비둘지 집 원리를 이용해 리퓨닛(repunit) 수들의 나머지를 비교하면, 9와 0으로만 구성된 n의 배수가 반드시 존재함을 증명할 수 있습니다.