C++로 디지털 루트가 X인 N번째 양수 찾기: 완전 탐색부터 O(1) 공식 풀이까지

이 문제에서는 두 개의 정수 N과 X가 주어지며, 우리의 목표는 디지털 루트가 X인 N번째 양수를 찾는 프로그램을 작성하는 것입니다.

디지털 루트(Digital Root)란?

디지털 루트는 어떤 수의 각 자릿수를 더하고, 그 합이 한 자리 숫자가 될 때까지 이 과정을 반복해서 얻은 한 자리 양의 정수를 의미합니다.

예를 들어 1234의 경우, 1+2+3+4 = 10이 되고, 다시 1+0 = 1이므로 디지털 루트는 1입니다.

문제 이해를 위한 예시

입력

N = 5, X = 4

출력

40

설명: 디지털 루트가 4인 양수는 4, 13, 22, 31, 40, ... 순서로 나타납니다. 따라서 5번째 해당하는 수는 40입니다.

방법 1: 완전 탐색(Brute Force)

가장 직관적인 해결 방법은 1부터 차례대로 수를 확인하면서, 현재 수의 디지털 루트가 X와 일치하는지 검사하고 조건을 만족하는 수의 개수를 세어 N번째 수를 찾는 것입니다.

알고리즘

• 1부터 시작하여 각 숫자의 디지털 루트를 계산합니다.
• 디지털 루트가 X와 같으면 카운터를 1 증가시킵니다.
• 카운터가 N에 도달하면 해당 숫자를 결과로 반환합니다.

예제 코드

#include <iostream>
using namespace std;

// 숫자의 디지털 루트를 계산하는 함수
int calcDigitalRoot(int num) {
    int digitSum = 1000, number = num;
    while (digitSum >= 10) {
        digitSum = 0;
        while (number > 0) {
            digitSum += number % 10;
            number /= 10;
        }
        number = digitSum;
    }
    return digitSum;
}

// 디지털 루트가 X인 N번째 양수를 찾는 함수
int calcNthDigitalRoot(int X, int N) {
    int countDigitalRootVals = 0;
    for (int i = 1; countDigitalRootVals < N; ++i) {
        if (calcDigitalRoot(i) == X)
            ++countDigitalRootVals;
        if (countDigitalRootVals == N)
            return i;
    }
    return -1;
}

int main() {
    int X = 4, N = 5;
    cout << "디지털 루트가 " << X << "인 " << N << "번째 양수는 "
         << calcNthDigitalRoot(X, N);
    return 0;
}

실행 결과

디지털 루트가 4인 5번째 양수는 40

이 방법은 정확하지만, N이 커질수록 매 숫자마다 자릿수 합을 반복적으로 계산해야 하므로 시간 복잡도가 O(N × log M)으로 증가하여 비효율적입니다.

방법 2: 수학적 공식을 활용한 효율적 풀이

디지털 루트가 X인 수들을 관찰해 보면 X, X+9, X+18, X+27, ...처럼 항상 9씩 증가하는 등차수열을 이룹니다. 이는 어떤 수에 9를 더해도 각 자릿수의 합이 9의 배수만큼 변할 뿐, 9로 나눈 나머지(즉, 디지털 루트)는 변하지 않기 때문입니다.

이 성질을 이용하면 반복 계산 없이 다음 공식으로 N번째 수를 바로 구할 수 있습니다.

N번째 수 = (N − 1) × 9 + X

단, 이 공식이 성립하려면 X는 1 이상 9 이하의 한 자리 양의 정수여야 합니다.

예제 코드

#include <iostream>
using namespace std;

// 공식을 이용해 디지털 루트가 X인 N번째 양수를 계산하는 함수
int calcNthDigitalRoot(int X, int N) {
    int nthNumber = ((N - 1) * 9) + X;
    return nthNumber;
}

int main() {
    int X = 4, N = 12;
    cout << "디지털 루트가 " << X << "인 " << N << "번째 양수는 "
         << calcNthDigitalRoot(X, N);
    return 0;
}

실행 결과

디지털 루트가 4인 12번째 양수는 103

검증해 보면 (12 − 1) × 9 + 4 = 99 + 4 = 103으로, 실제로 4, 13, 22, ..., 94, 103 중 12번째 값과 일치합니다.

두 방법의 복잡도 비교

결론적으로, 디지털 루트의 주기성(9의 주기)을 활용한 공식 풀이가 가장 효율적이며, N이 아무리 커져도 상수 시간 안에 답을 구할 수 있다는 것이 이 문제의 핵심 포인트입니다.