นับชุดของสามตัว (Triplets) ที่ผลรวมเป็นกำลังสามสมบูรณ์ใน C++

เราได้รับอาร์เรย์ของจำนวนเต็ม n ตัว งานคือการนับชุดของสามตัว (triplets) ที่ผลรวมเป็นกำลังสามสมบูรณ์ (perfect cube)

กำลังสามสมบูรณ์คืออะไร?

จำนวนที่เป็นกำลังสามของจำนวนเต็ม เช่น 1, 8, 27, 64, 125... (1³, 2³, 3³, 4³, 5³...)

เงื่อนไข: ผลรวมของ triplet อยู่ในขอบเขต 15000 ดังนั้นมีกำลังสามที่เป็นไปได้เพียง 24 ค่า (1³ ถึง 24³) จึงใช้ Dynamic Programming เพื่อลดความซับซ้อน

ตัวอย่าง

Input − array[] = {5, 2, 18, 6, 3} Output − Number of Triplets = 1

คำอธิบาย − 18+6+3 = 27 (3³) เป็น triplet 唯一ที่เป็นกำลังสาม

Input − array[] = {1, 2, 3, 4, 5} Output − Number of Triplets = 2

คำอธิบาย − 1+2+5=8 (2³), 1+3+4=8 (2³)

แนวทางการแก้ปัญหา (Dynamic Programming)

• สร้างตาราง DP arrd[i][j] เก็บความถี่ของค่า j ในอาร์เรย์ตั้งแต่ต้นถึงตำแหน่ง i
• คำนวณตาราง DP แบบ prefix sum
• วนลูปคู่ i, j หาค่า k ที่เป็นกำลังสาม (1³ ถึง 24³)
• คำนวณค่าที่ต้องการ: rem = k³ - (arr[i] + arr[j])
• ใช้ตาราง DP หาจำนวน rem ในช่วง j+1 ถึง n-1

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int dp[1001][15001];

void compute(int ar[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= 15000; j++) {
            if (i == 0) dp[i][j] = (j == ar[i]);
            else dp[i][j] = dp[i-1][j] + (ar[i] == j);
        }
    }
}

int countTriplets(int ar[], int n) {
    compute(ar, n);
    int ans = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = 1; k <= 24; k++) {
                int cube = k * k * k;
                int rem = cube - (ar[i] + ar[j]);
                if (rem > 0)
                    ans += dp[n-1][rem] - dp[j][rem];
            }
        }
    }
    return ans;
}

int main() {
    int ar[] = {5, 2, 18, 6, 3};
    int n = sizeof(ar) / sizeof(ar[0]);
    cout << "Number of Triplets = " << countTriplets(ar, n);
    return 0;
}

ผลลัพธ์

Number of Triplets = 1