숫자 N이 하나 주어졌을 때, 두 양수의 세제곱 합이 N과 같아지는 순서쌍(ordered pair)의 개수를 찾는 것이 목표입니다.
다시 말해 방정식 a3 + b3 = N을 만족하는 모든 (a, b) 조합을 구하면 됩니다. 이때 a는 N의 세제곱근(∛N) 이하 범위에서 탐색하고, b는 (N − a3)의 세제곱근으로 계산할 수 있습니다.
예시
입력
N=35
출력
Count of pairs of (a,b) where a^3+b^3=N: 2
설명
가능한 순서쌍은 (2, 3)과 (3, 2)입니다. 23 + 33 = 8 + 27 = 35이므로 총 2개입니다.
입력
N=100
출력
Count of pairs of (a,b) where a^3+b^3=N: 0
설명
조건을 만족하는 순서쌍이 존재하지 않습니다.
알고리즘 접근 방법
- 정수 N을 입력받습니다.
- cubeSum(int n) 함수는 n을 받아 세제곱의 합이 n이 되는 순서쌍의 개수를 반환합니다.
- 순서쌍 개수를 저장할 변수 count를 0으로 초기화합니다.
- for 루프를 사용해 a의 후보 값을 차례대로 확인합니다.
- a는 1부터 시작하여 a가 n의 세제곱근 cbrt(n)보다 작은 동안 반복합니다.
- b의 세제곱 값을 bcube = n − a3으로 계산합니다.
- b를 cbrt(bcube)로 구한 뒤, pow(b, 3) == bcube인지 검사합니다.
- 조건이 성립하면 bcube가 완전세제곱(perfect cube)이라는 뜻이므로 count를 1 증가시킵니다.
- 모든 반복이 끝나면 count에 조건을 만족하는 순서쌍의 총 개수가 저장됩니다.
- count를 결과값으로 반환합니다.
예제 코드
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int cubeSum(int n){
int count = 0;
for (int a = 1; a < cbrt(n); a++){
int bcube = n - (pow(a,3));
int b = cbrt(bcube);
if(pow(b,3) == bcube)
{ count++; }
}
return count;
}
int main(){
int N = 35;
cout << "Count of pairs of (a,b) where a^3+b^3=N: " << cubeSum(N);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of pairs of (a,b) where a^3+b^3=N: 2
참고 사항
cbrt()와 pow()는 부동소수점 연산을 수행하기 때문에 N이 클 경우 오차로 인해 잘못된 결과가 나올 수 있습니다. 실무에서는 비교 전에 round()로 반올림하거나 long long 자료형을 함께 사용하는 것이 안전합니다.
이 알고리즘은 a에 대해 한 번씩만 순회하므로 시간 복잡도는 O(∛N)입니다. 예를 들어 N이 1018처럼 매우 커도 약 100만 번의 반복으로 충분히 빠르게 답을 구할 수 있습니다.