C++에서 자기 자신과 자릿수의 합이 n이 되는 숫자 x 찾기

문제 소개

이번 글에서는 흥미로운 수학적 문제를 C++로 해결해 보겠습니다. 하나의 숫자 n이 주어졌을 때, x와 x의 각 자릿수의 합을 더한 값이 정확히 n이 되는 숫자 x를 찾아야 합니다.

예를 들어 n의 값이 21이라고 가정해 봅시다. 이때 프로그램은 x = 15를 반환해야 합니다. 그 이유는 15와 15의 자릿수의 합을 더하면 15 + 1 + 5 = 21, 즉 n과 같아지기 때문입니다.

해결 접근 방법

이 문제는 매우 단순한 방법으로 풀 수 있습니다. 핵심 로직은 다음과 같습니다.

1부터 n까지 모든 숫자를 차례대로 검사하면서, 현재 숫자와 그 숫자의 자릿수의 합을 더한 값이 n과 일치하는지 확인합니다. 조건을 만족하는 숫자를 발견하면 즉시 그 값을 반환하고, 끝까지 검사했는데도 찾지 못했다면 -1을 반환하여 답이 존재하지 않음을 알립니다.

자릿수의 합을 구하는 함수는 숫자를 10으로 나눈 나머지(일의 자리)를 계속 더하고, 몫으로 나누어 자릿수를 줄여가는 방식으로 구현할 수 있습니다.

예제 코드

#include<iostream>
using namespace std;

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

// 조건을 만족하는 숫자 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 << "The value of x is: " << getNumber(n);
}

실행 결과

The value of x is: 15

코드 설명 및 시간 복잡도

getDigitSum 함수는 입력받은 숫자의 자릿수의 합을 계산합니다. 10으로 나눈 나머지 연산(%)으로 일의 자리 숫자를 추출하여 누적하고, 나눗셈(/)으로 자릿수를 하나씩 제거합니다.

getNumber 함수는 0부터 n까지 반복하며 각 숫자 i에 대해 'i + i의 자릿수의 합'이 n과 같은지 검사합니다.

시간 복잡도를 살펴보면, 외부 루프가 최대 n번 실행되고 각 반복마다 자릿수의 합 계산에 약 O(log i)의 시간이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. n의 크기가 크지 않다면 충분히 효율적인 방법입니다.