C++로 X로 나누어 떨어지는 가장 큰 K자리 수 찾는 방법

이 튜토리얼에서는 X로 나누어 떨어지는 가장 큰 K자리 숫자를 찾는 프로그램을 C++로 작성해 보겠습니다.

문제 해결 과정은 생각보다 간단합니다. 수학적 성질을 활용하면 반복문 없이도 한 번의 계산으로 답을 구할 수 있습니다.

해결 접근 방식

다음 단계에 따라 문제를 해결할 수 있습니다.

• x와 k 값을 초기화합니다.
• pow(10, k) - 1을 계산합니다. 예를 들어 k가 7이라면 9,999,999가 되는데, 이것이 바로 가장 큰 K자리 숫자입니다.
• 위 값에서 x로 나눈 나머지를 빼주면, X로 나누어 떨어지는 가장 큰 K자리 숫자를 얻을 수 있습니다.

이 방법이 작동하는 이유는 간단합니다. 어떤 수에서 그 수를 x로 나눈 나머지를 빼면 결과값은 항상 x의 배수가 되기 때문입니다. 또한 가장 큰 K자리 숫자에서 나머지만큼만 줄어들었으므로, 여전히 K자리 범위 내에서 x로 나누어 떨어지는 최댓값이 됩니다.

예제 코드

실제 코드로 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int answer(int x, int k) {
    int max = pow(10, k) - 1; // 가장 큰 K자리 숫자
    return max - (max % x);   // 나머지를 빼서 x의 배수로 만듦
}

int main() {
    int x = 45, k = 7;
    cout << answer(x, k) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

9999990

x가 45이고 k가 7일 때, 9,999,990은 45로 나누어 떨어지는 가장 큰 7자리 숫자임을 확인할 수 있습니다.

마무리

이번 튜토리얼에서는 나머지 연산을 활용해 X로 나누어 떨어지는 가장 큰 K자리 숫자를 효율적으로 구하는 방법을 알아보았습니다. 시간 복잡도는 O(1)로 매우 효율적입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.