n개의 정수 배열이 주어지고 그 합이 완전 세제곱과 같은 모든 세 쌍의 개수를 계산하는 작업입니다.
완벽한 정육면체란 무엇입니까
완벽한 입방체는 임의의 수의 입방체인 숫자입니다. 예를 들어 125는 5의 입방체이므로 125는 완벽한 입방체라고 말할 수 있습니다. 완벽한 정육면체 정수 중 일부는 1, 8, 27, 64, 125….
따라서 배열의 문제에 따라 합이 완전한 입방체 수와 같은 트리플렛(3개 값의 집합)을 찾아서 계산해야 합니다. 또한 조건은 삼중항의 합이 최대 15000이므로 24개의 정육면체만 가능합니다. 따라서 우리는 덜 복잡하게 문제를 해결하기 위해 동적 프로그래밍 접근 방식을 사용할 것입니다.
예
Input− array[] = { 5, 2, 18, 6, 3 };
Output − Number of Triplets are= 1
Explanation − 18+6+3 = 27 (is a perfect cube)
Except this no other triplet is a perfect cube.
Input − array[] = {1, 2, 3, 4, 5};
Output − Number of Triplets are= 2
Explanation − 1 + 2 + 5 = 8 (is a perfect cube)
1 + 3 + 4 = 8 (is a perfect cube) 아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
양의 정수 배열 입력
-
크기 계산
-
동적 프로그래밍을 사용하여 배열에서 숫자의 발생을 찾습니다.
-
변수 a를 초기화하여 세 쌍의 개수를 저장합니다.
-
삼중항 집합의 세 번째 발생을 탐색하고 찾아 완벽한 정육면체인지 확인합니다. 삼중항이 완전 정육면체이면 ans의 값을 1만큼 증가시킵니다.
-
ans를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int arrd[1001][15001];
// Function to find the occurence of a number
// in the given range
void compute(int ar[], int num){
for (int i = 0; i < num; ++i) {
for (int j = 1; j <= 15000; ++j) {
// if i == 0
// assign 1 to present value
if (i == 0)
arrd[i][j] = (j == ar[i]);
// else add +1 to current state with
// previous state
else
arrd[i][j] = arrd[i - 1][j] + (ar[i] == j);
}
}
}
// Function to count the triplets whose sum
// is a perfect cube
int countTriplets(int ar[], int num){
compute(ar, num);
int ans = 0; // Initialize answer
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]);
// count all occurrence of third triplet
// in range from j+1 to n
if (rem > 0)
ans += arrd[num - 1][rem] - arrd[j][rem];
}
}
}
return ans;
}
// main function code
int main(){
int ar[] = { 5, 2, 18, 6, 3 };
int num = sizeof(ar) / sizeof(ar[0]);
cout << “Number of Triplets are= ”<<countTriplets(ar, num);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Number of Triplets are= 1