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

이 문제에서는 주어진 수 X로 나누어 떨어지는 가장 큰 K자리 숫자를 찾는 방법을 다룹니다. 접근 방식은 매우 간단합니다. 먼저 공식 ((10^k) − 1)을 이용해 가장 큰 K자리 숫자를 구한 뒤, 이 숫자가 X로 나누어 떨어지는지 확인합니다. 만약 나누어 떨어지지 않는다면 아래 공식을 사용해 정확한 답을 계산할 수 있습니다.

𝑚𝑎𝑥 − (𝑚𝑎𝑥 𝑚𝑜𝑑 𝑋)

동작 원리 예시

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

99999 − (99999 𝑚𝑜𝑑 29) = 99999 − 7 = 99992

계산 결과인 99992는 29로 나누어 떨어지는 가장 큰 5자리 숫자입니다.

알고리즘

maxKDigit(k, x)

begin
    max = (10^k) - 1
    if max가 x로 나누어 떨어지면 max 반환
    그렇지 않으면 max − (max mod x) 반환
end

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;
long max_k_digit(int k, int x){
    // k자리 최대 숫자 구하기
    int max = pow(10, k) - 1;
    if(max % x == 0){
        return max;
    }
    return (max) - (max % x);
}
main() {
    int k, x;
    cout << "자릿수(K)와 나누는 수(N) 입력: ";
    cin >> k >> x;
    cout << "결과: " << max_k_digit(k, x);
}

실행 결과

입력 예시 1:

자릿수(K)와 나누는 수(N) 입력: 5 29
결과: 99992

입력 예시 2:

자릿수(K)와 나누는 수(N) 입력: 6 87
결과: 999978

코드 설명

이 알고리즘의 시간 복잡도는 O(1)로 매우 효율적입니다. pow(10, k) − 1을 통해 K자리 최대값을 구하고, 모듈로 연산(%) 한 번만으로 조건을 만족하는 숫자를 즉시 계산할 수 있기 때문입니다. 단, K가 매우 커질 경우 정수 오버플로우에 유의해야 하며, 필요에 따라 long long 타입이나 문자열 기반 처리를 고려하는 것이 좋습니다.