C++로 x와 자릿수의 합이 n이 되는 수 x 찾는 방법

이번 글에서는 숫자 n이 주어졌을 때, 그 수 자신과 각 자릿수의 합을 더한 결과가 n과 같아지는 또 다른 수 x를 찾는 문제를 다뤄보겠습니다.

예를 들어 n의 값이 21이라면 정답은 x = 15입니다. 15의 자릿수 합은 1 + 5 = 6이고, 15 + 6 = 21이므로 조건을 만족하기 때문입니다.

문제 해결 접근 방법

이 문제는 아주 단순한 방법으로 풀 수 있습니다. 1부터 n까지의 모든 수를 차례로 검사하며, 현재 검사 중인 수 i에 대해 “i + i의 자릿수 합”이 n과 같은지 확인합니다. 조건을 만족하는 값을 찾는 즉시 해당 값을 반환하고, 끝까지 찾지 못했다면 -1을 반환합니다.

자릿수의 합은 수를 10으로 나눈 나머지(%)를 계속 더하고, 몫이 0이 될 때까지 반복하면 쉽게 구할 수 있습니다.

C++ 예제 코드

#include<iostream>
using namespace std;

// 숫자 n의 각 자릿수의 합을 구하는 함수
int getDigitSum(int n) {
   int sum = 0;
   while (n) {
      sum += n % 10;
      n /= 10;
   }
   return sum;
}

// 조건(x + 자릿수 합 == n)을 만족하는 x를 찾는 함수
int getNumber(int n) {
   for (int i = 0; i <= n; i++)
      if (i + getDigitSum(i) == n)
         return i;
   return -1;
}

int main() {
   int n = 21;
   cout << "x의 값: " << getNumber(n);
}

실행 결과

x의 값: 15

시간 복잡도 분석

위 알고리즘은 1부터 n까지 모든 후보를 검사하므로 시간 복잡도는 O(n × d)입니다. 여기서 d는 숫자의 자릿수입니다. n이 매우 클 경우에는 다소 비효율적일 수 있지만, 일반적인 입력 범위에서는 충분히 실용적이고 이해하기 쉬운 방법입니다.

참고: 생성자와 셀프 넘버

흥미롭게도 어떤 수 n을 만들어내는 이러한 수 x는 수학에서 ‘생성자(generator)’라고 불립니다. 그리고 생성자가 하나도 존재하지 않는 수는 ‘셀프 넘버(self number)’라고 하는데, 10진법에서 1, 3, 5, 7, 9 같은 한 자리 홀수가 대표적인 예입니다.