문제 개요
이 문제에서는 두 개의 값 K와 D가 주어집니다. 우리의 과제는 K자리 숫자를 출력하되, 그 숫자의 디지털 루트(digital root)가 정확히 D가 되도록 만드는 것입니다.
디지털 루트란 숫자의 각 자릿수를 계속해서 더해 나가, 마침내 한 자리 숫자가 될 때까지 반복했을 때 얻어지는 최종 값을 의미합니다. '디지털 합(digital sum)'이라고도 불립니다.
예시를 통해 문제를 살펴보겠습니다.
입력: D = 5, K = 6 출력: 500000
즉, 6자리 숫자이면서 각 자릿수의 합을 반복적으로 더했을 때 5가 되는 수를 찾으면 되는 것입니다.
해결 접근 방식
이 문제를 해결하는 가장 간단하고 우아한 방법은 숫자 D 뒤에 0을 채우는 것입니다. 즉, 우리가 만들 숫자는 {D000... (K-1개의 0)} 형태가 됩니다.
그 이유는 다음과 같습니다. D는 이미 한 자리 숫자이므로 그 자체로 디지털 루트가 D입니다. 여기에 0을 아무리 추가해도 0은 자릿수의 합에 영향을 주지 않기 때문에, 결과 숫자의 디지털 루트는 여전히 D로 유지됩니다. 덕분에 복잡한 연산 없이도 문제를 해결할 수 있으며, 구현 난이도와 시간 복잡도 모두 매우 낮습니다.
단, 한 가지 예외 상황이 있습니다. D가 0이면서 K가 1보다 큰 경우에는 답이 존재하지 않습니다. 첫 번째 자리는 0이 될 수 없고, 0이 아닌 다른 숫자를 넣으면 디지털 루트가 0이 될 수 없기 때문입니다. 이 경우에는 -1을 출력하도록 처리해야 합니다.
구현 예제
위에서 설명한 솔루션을 C++로 구현한 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
void printKdigitNumber(int k, int d) {
if (d == 0 && k != 1)
cout << "-1";
else {
cout << d;
k--;
while (k--)
cout << "0";
}
}
int main() {
int K=6, D=5;
cout<<K<<" digit number with digital Root = "<<D<<" is : ";
printKdigitNumber(K, D);
return 0;
}실행 결과
6 digit number with digital Root = 5 is : 500000
복잡도 분석
이 알고리즘은 숫자를 한 번씩만 출력하면 되므로 시간 복잡도는 O(K)이며, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 입력 크기와 무관하게 항상 빠르게 동작하는 효율적인 해결책입니다.