C++로 구현하는 X로 나누어 떨어지는 가장 작은 K자리 숫자 찾기

이 문제의 목표는 X로 나누어 떨어지는 가장 작은 K자리 숫자를 찾는 것입니다. 이를 위해 먼저 공식 10^(k-1)을 사용하여 가장 작은 K자리 숫자를 구합니다. 그다음 해당 숫자가 X로 나누어 떨어지는지 확인하고, 나누어 떨어지지 않는 경우에는 아래 공식을 활용해 정확한 값을 계산할 수 있습니다.

(min + X) − ((min + X) mod X)

예를 들어, 29로 나누어 떨어지는 5자리 숫자를 찾는다고 가정해 보겠습니다. 가장 작은 5자리 숫자는 10000이지만, 10000은 29로 나누어 떨어지지 않습니다. 이때 위 공식을 적용하면 다음과 같습니다.

(10000 + 29) − ((10000 + 29) mod 29) = 10029 − 24 = 10005

계산 결과인 10005가 바로 29로 나누어 떨어지는 가장 작은 5자리 숫자입니다.

동작 원리

이 공식이 작동하는 이유는 간단합니다. 최소값(min)에 X를 더한 값에서 그 값을 X로 나눈 나머지를 빼면, min보다 크면서 X의 배수가 되는 가장 작은 수를 얻게 됩니다. 즉, min을 기준으로 X의 배수 지점까지 올림(round up)하는 효과가 있는 셈입니다. 덕분에 반복문 없이 상수 시간(O(1)) 안에 답을 구할 수 있다는 것이 이 방법의 가장 큰 장점입니다.

알고리즘

minKDigit(k, x)

시작
    min = 10^(k-1)
    만약 min이 x로 나누어 떨어지면 min을 반환
    그렇지 않으면 (min + x) – ((min + x) mod x)를 반환
종료

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;
long min_k_digit(int k, int x) {
    // k자리 숫자 중 최솟값 구하기
    int min = pow(10, k-1);
    if(min % x == 0) {
        return min;
    }
    return (min + x) - ((min + x) % x);
}
main() {
    int k, x;
    cout << "Enter Digit Count(K) and Divisor(N): ";
    cin >> k >> x;
    cout << "Result is: " << min_k_digit(k, x);
}

실행 결과

Enter Digit Count(K) and Divisor(N): 5 29
Result is: 10005

Enter Digit Count(K) and Divisor(N): 6 87
Result is: 100050

위 실행 결과에서 확인할 수 있듯이, 자릿수(K)와 나누는 수(X)만 입력하면 조건을 만족하는 가장 작은 숫자가 즉시 출력됩니다. 참고로 K가 매우 커질 경우 pow 함수의 부동소수점 오차나 정수 오버플로우가 발생할 수 있으므로, 실무에서는 long long 타입 사용이나 문자열 기반 처리를 함께 고려하는 것이 좋습니다.