이 글에서는 하나의 정수(예: X)가 서로 다른(unique) 자연수들의 n제곱의 합으로 표현될 수 있는 모든 방법의 개수를 구하는 프로그램을 다룹니다.
예를 들어, X = 100이고 n = 2라고 가정해 보겠습니다.
이 경우 100은 자연수 제곱의 합으로 다음과 같이 세 가지 방법으로 표현할 수 있습니다.
100 = 102 100 = 62 + 82 100 = 12 + 32 + 42 + 52 + 72
접근 방법: 재귀 활용
이 문제는 재귀(recursion)를 사용하면 비교적 쉽게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 1부터 시작하여 주어진 숫자의 n제곱근(n-th root)까지 탐색합니다.
- 각 단계마다 자연수의 n제곱 값을 현재 남은 값에서 차감하며 재귀적으로 호출합니다.
- 중복된 자연수를 사용하지 않도록, 이전에 사용한 숫자보다 항상 큰 숫자만 선택합니다.
- 남은 값이 정확히 0이 되면 그것은 하나의 유효한 표현 방법이므로 결과 카운트를 증가시킵니다.
이 과정을 통해 주어진 정수를 자연수의 n제곱의 합으로 나타낼 수 있는 모든 조합의 개수를 얻을 수 있습니다.
C++ 구현 예제
#include<iostream>
#include <math.h>
using namespace std;
int result = 0;
int ways(int number, int a, int init, int n){
if (a == 0) {
result++;
}
// 상한값 설정: number의 n제곱근
int max = (int)floor(pow(number, 1.0 / n));
for (int i = init + 1; i <= max; i++) {
// 1부터 시작하는 n제곱 값을 차감
int b = a - (int)pow(i, n);
if (b >= 0)
ways(number, a - (int)pow(i, n), i, n);
}
return result;
}
int main() {
int a = 100, n = 2;
cout << ways(a, a, 0, n);
return 0;
}코드 설명
ways()함수는 네 개의 매개변수를 받습니다: 원래 숫자(number), 현재 남은 값(a), 마지막으로 사용한 자연수(init), 지수(n)입니다.- 남은 값
a가 0이 되면 유효한 표현을 찾은 것이므로 전역 변수result를 1 증가시킵니다. floor(pow(number, 1.0 / n))을 통해 탐색 범위의 상한을 계산합니다.- 루프에서는
init + 1부터 시작하여 이미 사용한 숫자보다 큰 값만 고려함으로써 각 자연수가 한 번씩만 사용되도록 보장합니다.
실행 결과
3
X = 100, n = 2인 경우 앞서 확인한 것처럼 세 가지 표현 방법이 존재하므로 프로그램은 3을 출력합니다.