문제 개요
주어진 정수 X에 대해, X로 나누어 떨어지면서 자릿수가 정확히 K인 가장 작은 숫자를 구하는 프로그램을 작성하는 것이 목표입니다. 이 문제는 반복문 없이 간단한 수학 공식 하나만으로 해결할 수 있으며, 시간 복잡도는 O(1)입니다.
해결 접근 방식
공식은 다음 순서로 동작합니다.
- K자리 최솟값 계산: K자리 숫자 중 가장 작은 값은 10^(K−1)입니다. 예를 들어 K가 2라면 10, K가 3이라면 100, K가 5라면 10000이 됩니다.
- 나눗셈 검사: 이 최솟값(min)이 X로 나누어 떨어지는지 확인합니다. 나머지가 0이라면 min이 곧 정답입니다.
- 나머지 보정: 나누어 떨어지지 않는다면 아래 공식으로 정답을 구합니다.
answer = (min + X) - ((min + X) % X)
이 식은 min 이상인 수 중에서 X의 배수인 첫 번째 값을 의미합니다. min에 X를 더한 뒤 그 값을 X로 나눈 나머지를 빼면, 조건을 만족하는 가장 가까운 X의 배수를 얻을 수 있기 때문입니다.
예제 코드
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int X = 83;
int K = 5;
// K자리 숫자 중 최솟값 (K=5이면 10000)
int MIN = pow(10, K - 1);
cout << X << "으로 나누어 떨어지는 가장 작은 " << K << "자리 숫자는 ";
if (MIN % X == 0)
cout << MIN;
else
cout << ((MIN + X) - ((MIN + X) % X));
return 0;
}
실행 결과
83으로 나누어 떨어지는 가장 작은 5자리 숫자는 10043
코드 동작 설명
예제에서 min은 10000이며, 10000을 83으로 나누면 나머지가 남습니다. 따라서 (10000 + 83) - ((10000 + 83) % 83) = 10083 - 40 = 10043이 정답이 됩니다. 실제로 83 × 121 = 10043이므로, 10043은 83의 배수이면서 조건을 만족하는 가장 작은 5자리 숫자입니다.
시간 복잡도
이 방법은 탐색이나 반복문 없이 산술 연산만 사용하므로 전체 시간 복잡도는 O(1)입니다. 입력 크기와 관계없이 항상 일정한 성능을 보장하기 때문에 매우 효율적인 접근 방식입니다.