C++로 두 수의 거듭제곱 합이 bound 이하인 모든 정수 구하기

문제 개요

이 문제에서는 두 개의 숫자 a와 b, 그리고 하나의 정수 bound가 주어집니다. 우리가 해야 할 일은 bound 이하의 값 중에서 a와 b의 거듭제곱의 합으로 표현할 수 있는 모든 정수를 찾아 출력하는 것입니다.

수식으로 표현하면 다음 조건을 만족하는 모든 값을 구해야 합니다.

bound >= aⁱ + b^j

예제

예제를 통해 문제를 더 쉽게 이해해 보겠습니다.

입력: a = 2, b = 3, bound = 8
출력: 2 3 4 5 7

위 출력값은 다음과 같이 만들어집니다.

2⁰ + 3⁰ = 2
2¹ + 3⁰ = 3
2⁰ + 3¹ = 4
2² + 3⁰ = 5
2² + 3¹ = 7

접근 방법

이 문제는 0부터 시작하는 두 변수 i와 j를 사용하는 중첩 루프(nested loop)로 해결할 수 있습니다.

외부 루프: xⁱ가 bound 이상이 되면 종료합니다.
내부 루프: xⁱ + y^j가 bound를 초과하면 종료합니다.

내부 루프의 각 반복에서 계산된 xⁱ + y^j 값을 정렬된 집합(std::set)에 저장합니다. C++의 set 컨테이너는 자동으로 중복을 제거하고 오름차순으로 정렬해 주기 때문에, 별도의 정렬 과정 없이도 깔끔한 결과를 얻을 수 있다는 장점이 있습니다. 모든 연산이 끝나면 집합에 저장된 값들을 차례대로 출력하면 됩니다.

C++ 구현 예제

위 접근 방법을 실제로 구현한 프로그램은 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
void powerSum(int x, int y, int bound) {
    set<int> sumOfPowers;
    vector<int> powY;
    int i;
    powY.push_back(1);
    for (i = y; i < bound; i = i * y)
        powY.push_back(i);
    i = 0;
    while (true) {
        int powX = pow(x, i);
        if (powX >= bound)
            break;
        for (auto j = powY.begin(); j != powY.end(); ++j) {
            int num = powX + *j;
            if (num <= bound)
                sumOfPowers.insert(num);
            else
                break;
        }
        i++;
    }
    set<int>::iterator itr;
    for (itr = sumOfPowers.begin(); itr != sumOfPowers.end(); itr++) {
        cout<<*itr <<" ";
    }
}
int main() {
    int x = 2, y = 3, bound = 25;
    cout<<"Sum of powers of "<<x<<" and "<<y<<" less than "<<bound<<" are :
";
    powerSum(x, y, bound);
    return 0;
}

실행 결과

Sum of powers of 2 and 3 less than 25 are −
2 3 4 5 7 9 10 11 13 17 19 25

정리

이 알고리즘은 x와 y의 거듭제곱 값을 미리 계산해 두고, 가능한 모든 조합의 합을 set에 삽입하는 방식으로 동작합니다. set이 중복과 정렬을 자동으로 처리해 주기 때문에 구현이 단순하면서도 결과의 신뢰성을 보장할 수 있습니다. bound의 크기에 따라 탐색 범위가 제한되므로, 입력 값이 클 경우에도 비교적 효율적으로 동작합니다.