파이썬으로 X로 나누어 떨어지는 가장 작은 K자리 수 구하기

이 글에서는 주어진 문제를 해결하기 위한 풀이 방법과 접근 방식을 살펴봅니다.

문제 정의

정수 X(나누는 수)와 K(자릿수)가 주어졌을 때, X로 나누어 떨어지는 가장 작은 K자리 수를 구해야 합니다.

접근 방법

문제 해결 과정은 다음과 같습니다.

1. 먼저 최솟값(MIN), 즉 가장 작은 K자리 수를 계산합니다. 이 값은 10의 (K-1)제곱과 같습니다. 예를 들어 K가 4라면 MIN은 1000이 됩니다.
2. 만약 MIN을 X로 나눈 나머지가 0이라면, MIN 자체가 곧 정답입니다.
3. 그렇지 않다면, 정답은 다음 식으로 구할 수 있습니다.
   (MIN + X) − ((MIN + X) % X)

이 방법이 성립하는 이유는 [MIN ... MIN+X] 범위 안에는 반드시 X의 배수가 하나 존재하기 때문입니다.

구현 예제

def answer(k, x):
    # 가장 작은 k자리 수(MIN) 계산
    min_val = pow(10, k-1)
    if(min_val % x == 0):
        return min_val
    else:
        return ((min_val + x) - ((min_val + x) % x))

x = 83
k = 5
print(answer(k, x))

출력 결과

10043

위 코드에서 나누는 수 x를 83, 자릿수 k를 5로 설정하면 10000부터 시작하는 5자리 수 중 83으로 나누어 떨어지는 가장 작은 수인 10043이 출력됩니다. 실제로 83 × 121 = 10043이므로 결과가 올바른 것을 확인할 수 있습니다.

결론

이 글에서는 나누는 수 X와 자릿수 K가 주어졌을 때, X로 나누어 떨어지는 가장 작은 K자리 수를 구하는 방법을 알아보았습니다. 나머지 연산(%)만 활용하면 반복문 없이도 단 한 번의 계산으로 정답을 구할 수 있어 매우 효율적인 알고리즘입니다.