특정 디지털 루트를 가진 범위 내 숫자를 찾는 C++ 프로그램

디지털 루트란 무엇일까요?

어떤 수의 각 자릿수를 모두 더했을 때 그 합이 한 자리 수가 된다면, 이 값을 해당 수의 디지털 루트(Digital Root)라고 합니다. 예를 들어 25의 자릿수 합은 2+5=7이므로, 25의 디지털 루트는 7입니다.

이번 글에서 다룰 문제는 다음과 같습니다. 범위 [l, r]와 한 자리 정수 X가 주어졌을 때, 이 범위 안에서 디지털 루트가 X와 같은 수가 몇 개 있는지 구하는 것입니다.

입력: l = 13, r = 25, X = 4
출력: 2
설명: 범위 (13, 25)에서 자릿수 합이 4인 수는 13과 22입니다.

입력: l = 11, r = 57, X = 3
출력: 6

문제 해결 접근 방법

1. 단순한 접근 방식

가장 직관적인 방법은 l부터 r까지의 모든 수를 하나씩 순회하면서 각 수의 자릿수 합이 X와 일치하는지 확인하는 것입니다. 하지만 이 방식의 시간 복잡도는 O(N)(N은 범위 내 전체 수의 개수)이므로, 범위가 매우 넓어지면 비효율적입니다.

2. 효율적인 접근 방식

여기서 중요한 수학적 성질 하나를 활용할 수 있습니다. 어떤 수의 디지털 루트는 항상 그 수를 9로 나눈 나머지(num % 9)와 같으며, 나머지가 0일 경우 디지털 루트는 9가 됩니다.

따라서 X가 9라면 이를 0으로 바꾼 뒤 비교하면 됩니다. 전체 범위를 9개씩 묶은 그룹으로 나누면, 각 그룹 안에는 num % 9 == X를 만족하는 수가 정확히 하나씩 존재합니다. 즉, 그룹의 개수만큼 답에 더해주고, 마지막에 그룹에 속하지 못하고 남은 수들만 개별적으로 조건을 검사하면 됩니다. 이렇게 하면 범위가 아무리 커도 거의 상수 시간 만에 답을 구할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
    int l = 13;
    int r = 25;
    int X = 4;
    if (X == 9) X = 0; // X가 9라면 0으로 변경
    // 범위 내 전체 수의 개수
    int total = r - l + 1;
    // 수들을 최대 9개씩 그룹으로 나눔
    int groups = total / 9;
    // N개의 그룹마다 num % 9 == X인 수가 정확히 N개 존재
    int result = groups;
    // 그룹에 포함되지 않고 남은 수의 개수
    int left_out = total % 9;
    // 남은 각 수에 대해 조건을 개별적으로 검사
    for (int i = r; i > r - left_out; i--) {
        int rem = i % 9;
        if (rem == X)
            result++;
    }
    cout << "범위 (l, r)에서 주어진 디지털 루트(X)를 가진 수의 총 개수: " << result;
    return 0;
}

실행 결과

범위 (l, r)에서 주어진 디지털 루트(X)를 가진 수의 총 개수: 2

마무리

이번 튜토리얼에서는 주어진 범위와 디지털 루트 X가 있을 때, 범위 내에서 디지털 루트가 X인 모든 수를 찾는 문제를 살펴보았습니다. 단순히 모든 수를 순회하는 방법과, 수들을 9개씩 그룹으로 나누어 해결하는 효율적인 방법 두 가지를 함께 다루었습니다.

각 그룹에는 디지털 루트가 X인 수가 정확히 하나씩 존재한다는 성질 덕분에, 범위가 아무리 커져도 빠르게 답을 구할 수 있습니다. 이 로직은 C++뿐만 아니라 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.