X로 나누어 떨어지는 가장 큰 K자리 수를 구하는 C++ 프로그램

두 개의 정수 X와 K가 주어집니다. 여기서 K는 자릿수를 의미합니다. 이 문제의 목표는 X로 나누어 떨어지는 가장 큰 K자리 수를 찾는 것입니다.

입력: X = 30, K = 3
출력: 980

문제 풀이 접근 방법

30으로 나누어 떨어지는 가장 큰 세 자리 수는 980입니다.

이 문제를 해결하는 핵심 아이디어는 다음과 같습니다.

먼저 10을 K제곱한 값에서 1을 빼면 가장 큰 K자리 수를 구할 수 있습니다. 예를 들어 K가 3이라면 10³ − 1 = 999가 됩니다.

그다음 이 최댓값에서 X로 나눈 나머지를 빼주면, X의 배수 중에서 해당 자릿수 범위 내에 있는 가장 큰 수를 얻을 수 있습니다. 즉, MAX - (MAX % X) 공식을 사용하면 원하는 결과가 나옵니다.

C++ 구현 예제

#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int X = 20;
    int K = 3;
    int MAX = pow(10, K) - 1;
    cout << (MAX - (MAX % X));
}

코드 동작 원리

위 코드에서 MAX는 가장 큰 K자리 수(999)를 저장합니다. 그리고 MAX % X는 MAX를 X로 나눴을 때의 나머지이므로, 이 값을 빼면 X로 정확히 나누어 떨어지는 가장 큰 K자리 수가 계산됩니다.

예를 들어 X = 20인 경우, 999를 20으로 나눈 나머지는 19이므로 999 − 19 = 980이 출력됩니다. 시간 복잡도는 O(1)로 매우 효율적입니다.