정수 n개로 이루어진 배열이 주어졌을 때, 세 원소의 합이 완전세제곱수(perfect cube)가 되는 모든 삼중항(triplet)의 개수를 계산하는 것이 이 글의 목표입니다.
완전세제곱수란?
완전세제곱수는 어떤 수를 세 번 곱했을 때 얻어지는 수를 의미합니다. 예를 들어 125는 5의 세제곱이므로 완전세제곱수라고 할 수 있습니다. 대표적인 완전세제곱수로는 1, 8, 27, 64, 125 등이 있습니다.
따라서 이 문제에서는 배열 안에서 그 합이 완전세제곱수가 되는 삼중항(3개 값의 조합)을 찾아 개수를 세어야 합니다. 여기서 삼중항의 합은 최대 15000이라는 조건이 주어지므로, 가능한 세제곱수는 24개(1³부터 24³까지)뿐입니다. 이 특성을 활용하면 동적 계획법(Dynamic Programming)을 적용해 낮은 시간 복잡도로 문제를 해결할 수 있습니다.
예시
입력 − array[] = { 5, 2, 18, 6, 3 };
출력 − 삼중항의 개수 = 1
설명 − 18 + 6 + 3 = 27 (완전세제곱수)
이 외에는 합이 완전세제곱수가 되는 삼중항이 없습니다.
입력 − array[] = {1, 2, 3, 4, 5};
출력 − 삼중항의 개수 = 2
설명 − 1 + 2 + 5 = 8 (완전세제곱수)
1 + 3 + 4 = 8 (완전세제곱수)프로그램에 적용된 접근 방식
양의 정수로 이루어진 배열을 입력받습니다.
배열의 크기를 계산합니다.
동적 계획법을 이용해 배열 내 각 숫자의 누적 등장 횟수를 미리 계산해 둡니다.
삼중항의 개수를 저장할 변수 ans를 초기화합니다.
배열을 탐색하며 첫 두 원소를 고정한 뒤, 세 번째 원소가 될 수 있는 값의 개수를 조회하여 완전세제곱수를 만족하는지 확인하고, 만족한다면 ans를 1씩 증가시킵니다.
최종적으로 ans를 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int arrd[1001][15001];
// 주어진 범위에서 숫자의
// 등장 횟수를 계산하는 함수
void compute(int ar[], int num){
for (int i = 0; i < num; ++i) {
for (int j = 1; j <= 15000; ++j) {
// i == 0인 경우
// 현재 값에 1을 할당
if (i == 0)
arrd[i][j] = (j == ar[i]);
// 그 외의 경우 현재 상태에
// 이전 상태를 더함
else
arrd[i][j] = arrd[i - 1][j] + (ar[i] == j);
}
}
}
// 합이 완전세제곱수인
// 삼중항의 개수를 세는 함수
int countTriplets(int ar[], int num){
compute(ar, num);
int ans = 0; // 답 초기화
for (int i = 0; i < num - 2; ++i) {
for (int j = i + 1; j < num - 1; ++j) {
for (int k = 1; k <= 24; ++k) {
int cube = k * k * k;
int rem = cube - (ar[i] + ar[j]);
// j+1부터 n까지 범위에서
// 세 번째 원소의 모든 등장 횟수를 셈
if (rem > 0)
ans += arrd[num - 1][rem] - arrd[j][rem];
}
}
}
return ans;
}
// main 함수 코드
int main(){
int ar[] = { 5, 2, 18, 6, 3 };
int num = sizeof(ar) / sizeof(ar[0]);
cout << "삼중항의 개수 = " << countTriplets(ar, num);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
삼중항의 개수 = 1