C++로 거듭제곱의 합으로 숫자를 표현하는 방법의 수 구하기

두 개의 정수 num과 power가 입력으로 주어졌을 때, num을 서로 다른 자연수들을 주어진 거듭제곱한 값들의 합으로 표현할 수 있는 방법의 수를 구하는 것이 목표입니다.

예를 들어 num이 10이고 power가 2라면, 10은 1² + 3²로 표현할 수 있으므로 총 1가지 방법이 존재합니다.

입력 예시

num=30

출력

거듭제곱의 합으로 숫자를 표현하는 방법의 수: 2

설명

30을 거듭제곱의 합으로 표현하는 방법:
1² + 2² + 5² 와 1² + 2² + 3² + 4²

입력 예시

num=35

출력

거듭제곱의 합으로 숫자를 표현하는 방법의 수: 1

설명

num을 거듭제곱의 합으로 표현하는 방법: 2² + 3²

접근 방식

이 문제는 재귀(Recursion)를 활용하여 해결할 수 있습니다. 먼저 해당 숫자 자체가 어떤 수의 power 거듭제곱 값인지 확인합니다. 만약 그렇다면 방법의 수로 1을 반환하고, 그렇지 않다면 num^power + (num+1)^power 형태의 합을 재귀적으로 탐색합니다.

두 개의 정수 num과 power를 입력받습니다.
함수 sum_of_powers(int num, int power, int val)는 num을 받아서, 서로 다른 자연수를 주어진 거듭제곱한 값들의 합으로 num을 표현하는 방법의 수를 반환합니다.
check = (num - pow(val, power))를 계산합니다. 만약 check가 0이라면, 그 숫자 자체가 val^power이므로 1을 반환합니다.
check가 0보다 작다면 더 이상 표현이 불가능하므로 0을 반환합니다.
그 외의 경우에는 temp = val + 1로 설정합니다.
sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp)의 합을 반환합니다. 전자는 현재 값을 포함하는 경우, 후자는 포함하지 않는 경우를 의미합니다.
재귀 호출이 모두 끝나면 최종적으로 방법의 수를 얻게 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int sum_of_powers(int num, int power, int val){
    int check = (num - pow(val, power));
    if(check == 0){
        return 1;
    }
    else if(check < 0){
        return 0;
    } else {
        int temp = val + 1;
        return sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp);
    }
}
int main(){
    int num = 25, power = 2;
    cout<<"거듭제곱의 합으로 숫자를 표현하는 방법의 수: "<<sum_of_powers(num, power, 1);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

거듭제곱의 합으로 숫자를 표현하는 방법의 수: 2

위 예제에서 num=25, power=2일 때, 25는 3² + 4² 또는 5²로 표현할 수 있으므로 총 2가지 방법이 존재함을 확인할 수 있습니다.