C++에서 D로 나누어 떨어지는 N자리 숫자 찾기 방법

두 개의 정수 N과 D가 주어졌을 때, D로 나누어 떨어지는 N자리 숫자를 찾아야 합니다. 예를 들어 N이 3이고 D가 5라면, 답은 500이 될 수 있습니다.

이 문제는 생각보다 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. D의 자릿수를 m이라고 할 때, D 뒤에 (N − m)개의 0을 붙이면 결과적으로 N자리 숫자가 되며, 이 숫자는 자연스럽게 D로 나누어 떨어집니다.

단, 예외적인 경우도 존재합니다. 만약 D가 10처럼 두 자리 이상인데 N이 1이라면, 한 자리 숫자 중에서 D로 나누어 떨어지는 수를 만들 수 없으므로 답을 구하는 것이 불가능합니다.

접근 방법

1. D가 10보다 작은 경우(한 자리 숫자): D를 문자열로 변환한 뒤, 뒤에 (N − 1)개의 '0'을 붙입니다.
2. D가 10 이상인 경우:
   • N이 1이면 조건을 만족하는 숫자가 없으므로 "Cannot find any number"를 반환합니다.
   • N이 2 이상이면 D를 문자열로 변환하고, 뒤에 (N − m)개의 '0'을 붙입니다. 여기서 m은 D의 자릿수입니다.

C++ 구현 예제

#include<iostream>
using namespace std;
string nDigitDivByD(int n, int d) {
    string ans = "";
    if (d < 10) {
        ans += to_string(d);
        for (int i = 1; i < n; i++)
            ans += "0";
    }
    else {
        if (n == 1)
            return "Cannot find any number";
        else {
            string temp = to_string(d);
            ans += to_string(d);
            for (int i = 0; i < n-temp.length(); i++)
                ans += "0";
        }
    }
    return ans;
}
int main() {
    int n = 5, d = 15;
    cout << nDigitDivByD(n, d);
}

출력 결과

15000

위 예제에서 N은 5, D는 15입니다. D인 15는 두 자리 숫자이므로(m = 2), 뒤에 3개의 0을 붙여 15000을 얻습니다. 15000은 5자리 숫자이면서 15로 나누어 떨어지므로 올바른 답입니다.

시간 복잡도

이 알고리즘은 단순히 문자열에 0을 이어 붙이는 작업만 수행하므로 시간 복잡도는 O(N)입니다. 별도의 반복 탐색이나 복잡한 연산이 필요 없기 때문에 매우 효율적입니다.