C++로 주어진 방정식의 해 개수 효율적으로 구하기

이 문제에서는 세 개의 정수 A, B, C가 주어지며, 우리의 목표는 주어진 방정식을 만족하는 해의 개수를 구하는 것입니다.

방정식

X = B*Sm(X)^A + C

여기서 Sm(X)는 X의 각 자릿수의 합을 의미합니다.

X는 1부터 10⁹ 사이의 어떤 수든 될 수 있으며, 이 범위 내에서 위 방정식을 만족하는 모든 X의 개수를 세어야 합니다.

예시를 통해 문제를 이해해 봅시다,

입력

A = 3, B = 6, C = 4

출력

3

해결 접근 방식

이 문제를 해결하는 핵심 열쇠는 바로 자릿수의 합입니다. X의 최댓값은 999,999,999이므로, 자릿수의 합이 가질 수 있는 최댓값은 9×9 = 81입니다. 즉, 가능한 자릿수의 합은 1부터 81까지 총 81가지뿐입니다.

각 자릿수의 합 값에 대해 방정식에 대입했을 때 나오는 후보 해 X = B*digSum^A + C를 계산하고, 이 값의 실제 자릿수 합이 처음 가정한 digSum과 일치하는지 확인하면 됩니다. 일치한다면 그 값은 유효한 해이며, 추가로 X가 10⁹ 미만인지만 검사하면 됩니다.

이러한 방식으로 반복 횟수를 최대 81회로 제한할 수 있어, 무작정 10억 개의 값을 하나씩 검사하는 것보다 압도적으로 효율적인 알고리즘이 완성됩니다.

예제 코드

아래는 위 접근 방식의 동작을 보여주는 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
int countSolutions(int a, int b, int c){
    int solutionCount = 0;
    // 자릿수의 합을 1부터 81까지 시도
    for (int digSum = 1; digSum <= 81; digSum++) {
        int solVal = b * pow(digSum, a) + c; // 후보 해 계산
        int temp = solVal;
        int sum = 0;
        while (temp) { // 실제 자릿수의 합 계산
            sum += temp % 10;
            temp /= 10;
        }
        // 가정한 자릿수의 합과 일치하고 범위 내인 경우
        if (sum == digSum && solVal < 1e9)
            solutionCount++;
    }
    return solutionCount;
}
int main(){
    int a = 3, b = 6, c = 4;
    cout<<"The number of solutions of the equations is "<<countSolutions(a, b, c);
    return 0;
}

실행 결과

The number of solutions of the equations is 3

A = 3, B = 6, C = 4일 때 방정식을 만족하는 해는 총 3개입니다. 이처럼 자릿수의 합이라는 제약 조건을 역으로 활용하면, 넓은 탐색 범위를 아주 작은 반복으로 줄여 문제를 빠르게 해결할 수 있습니다.