이 튜토리얼에서는 하나의 정수가 중복되지 않는 자연수들의 n제곱의 합으로 표현될 수 있는 경우의 수를 구하는 프로그램을 작성해 보겠습니다.
두 개의 정수 number와 power가 주어졌을 때, 주어진 number를 서로 다른 자연수들의 n제곱의 합으로 나타낼 수 있는 방법이 총 몇 가지인지 구해야 합니다. 예시를 통해 살펴보겠습니다.
입력 − number = 50, power = 2
출력 − 3
50은 다음과 같이 세 가지 방법으로 표현할 수 있습니다.
- 1² + 7² = 1 + 49 = 50
- 3² + 4² + 5² = 9 + 16 + 25 = 50
- 1² + 2² + 3² + 6² = 1 + 4 + 9 + 36 = 50
이 문제는 재귀(recursion)를 이용해 해결할 수 있습니다. 문제 해결 단계를 하나씩 살펴보겠습니다.
- number와 power를 초기화합니다.
- 적절한 이름의 재귀 함수를 작성합니다. 이 함수는 number, power, 그리고 i를 인자로 받습니다.
- number가 0보다 작거나 pow(i, power)가 number보다 크면 0을 반환합니다. 더 이상 유효한 조합이 없다는 의미입니다.
- number가 0이거나 pow(i, power)가 number와 정확히 같으면 1을 반환합니다. 하나의 유효한 표현을 찾았다는 의미입니다.
- 총 경우의 수를 계산하기 위해 두 번의 재귀 호출을 수행합니다.
- i를 1 증가시킵니다.
- 첫 번째 재귀 호출에서는 현재 수 i의 제곱을 선택하는 경우(number에서 pow(i, power)를 뺀 값)를 탐색합니다.
- 두 번째 재귀 호출에서는 현재 수 i를 건너뛰는 경우를 탐색합니다.
즉, 각 자연수마다 '포함한다'와 '포함하지 않는다' 두 가지 선택지를 모두 고려하면서 모든 조합을 탐색하는 방식입니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int findPossibleWaysCount(int number, int power, int i = 1) {
if(number < 0 || number < pow(i, power)) {
return 0;
}
if(number == 0 || number == pow(i, power)) {
return 1;
}
return findPossibleWaysCount(number - pow(i, power), power, i + 1)
+ findPossibleWaysCount(number, power, i + 1);
}
int main() {
// number와 power 초기화
int number = 50, power = 2;
cout << findPossibleWaysCount(number, power) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
3
마무리
이처럼 재귀 함수를 활용하면 각 자연수를 포함하거나 제외하는 모든 경우를 체계적으로 탐색하여 원하는 경우의 수를 손쉽게 구할 수 있습니다. 이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.