C++로 마법 수(Magic Number) 판별하기 – 자릿수의 재귀적 합이 1인지 확인하는 방법

마법 수(Magic Number)란 무엇인가?

이번 글에서는 어떤 숫자가 마법 수(Magic Number)인지 판별하는 프로그램을 살펴보겠습니다. 마법 수란 각 자릿수의 합을 한 자리 숫자가 될 때까지 반복해서 더했을 때 최종 결과가 1이 되는 수를 말합니다.

예를 들어 숫자 50311을 살펴보겠습니다.

5 + 0 + 3 + 1 + 1 = 10
1 + 0 = 1

최종적으로 1이 되므로 50311은 마법 수입니다.

판별 방법

어떤 수가 마법 수인지 확인하려면 다음 과정을 따릅니다.

1. 숫자의 모든 자릿수를 더한다.
2. 그 합이 두 자리 이상이면, 다시 그 숫자의 자릿수를 더한다.
3. 한 자리 숫자가 남을 때까지 위 과정을 반복한다.
4. 최종 값이 1이면 마법 수, 그렇지 않으면 마법 수가 아니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int isMagicNumber(int n) {
    int digit_sum = 0;
    while (n > 0 || digit_sum > 9) {
        if (n == 0) {
            n = digit_sum;   // 지금까지의 자릿수 합을 새로운 숫자로 사용
            digit_sum = 0;
        }
        digit_sum += n % 10; // 마지막 자릿수를 더함
        n /= 10;             // 마지막 자릿수 제거
    }
    return (digit_sum == 1);
}

int main() {
    int number = 50311;
    if (isMagicNumber(number)) {
        cout << number << " is magic number";
    } else {
        cout << number << " is not magic number";
    }
}

실행 결과

50311 is magic number

코드 설명

위 코드의 핵심은 isMagicNumber() 함수입니다. 이 함수는 while 루프 안에서 다음과 같이 동작합니다.

- n % 10으로 현재 숫자의 마지막 자릿수를 구해 digit_sum에 누적합니다.
- n /= 10으로 마지막 자릿수를 제거합니다.
- n이 0이 되었는데도 digit_sum이 아직 두 자리 이상이라면(digit_sum > 9), 자릿수 합을 새로운 n으로 설정하고 과정을 반복합니다.
- 루프가 끝나면 digit_sum은 반드시 한 자리 숫자이며, 이 값이 1이면 마법 수입니다.

참고: 디지털 루트(Digital Root)와의 관계

자릿수의 합을 한 자리가 될 때까지 반복해 구한 값을 디지털 루트(digital root)라고 부릅니다. 즉, 마법 수란 디지털 루트가 1인 수라고 정의할 수 있습니다.

수학적으로는 디지털 루트가 9의 배수 성질을 따르기 때문에, 양의 정수 n에 대해 n % 9 == 1이면 마법 수라는 것을 O(1) 시간에 바로 판별할 수도 있습니다. 다만 위의 반복 계산 방식은 알고리즘 학습 및 면접에서 자주 요구되는 기본적인 구현 방법이므로 함께 익혀두는 것이 좋습니다.