ตรวจสอบตัวเลขใหญ่แบ่งเซกเมนต์ได้ผลรวมเท่ากันใน C++

ปัญหา

ให้ตัวเลขขนาดใหญ่ (string) ตรวจสอบว่าแบ่งเป็น 2 เซกเมนต์ขึ้นไป ได้ โดยแต่ละเซกเมนต์มีผลรวมหลักเท่ากัน

ตัวอย่าง: "74325" → เซกเมนต์ (7), (4,3), (2,5) → ผลรวมแต่ละคู่ = 7 ✓

อัลกอริทึม: Prefix Sum + Greedy

1. คำนวณ Prefix Sum ของหลักต่างๆ
2. ลองทำให้เซกเมนต์แรกสิ้นสุดที่ตำแหน่ง i (i = 0 ถึง n-2)
3. targetSum = prefixSum[i]
4. ท่องต่อจาก i+1 สะสมผลรวม:
   • ถ้าผลรวม == targetSum → เริ่มเซกเมนต์ใหม่ (reset sum=0)
   • ถ้าผลรวม > targetSum → แบ่งไม่ได้ break
5. ถ้าจบครบและ sum=0 และมีอย่างน้อย 2 เซกเมนต์ → สำเร็จ

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

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool canBeSegmented(const string& str) {
    int n = str.length();
    if (n < 2) return false;
    
    // Prefix sum
    vector<int> prefix(n);
    prefix[0] = str[0] - '0';
    for (int i = 1; i < n; i++)
        prefix[i] = prefix[i-1] + (str[i] - '0');
    
    // ลองจุดตัดเซกเมนต์แรก
    for (int i = 0; i < n - 1; i++) {
        int target = prefix[i];
        int currSum = 0;
        int segments = 1; // เซกเมนต์แรก
        bool valid = true;
        
        for (int j = i + 1; j < n; j++) {
            currSum += str[j] - '0';
            if (currSum == target) {
                segments++;
                currSum = 0;
            } else if (currSum > target) {
                valid = false;
                break;
            }
        }
        
        if (valid && currSum == 0 && segments >= 2)
            return true;
    }
    return false;
}

int main() {
    string tests[] = {"74325", "123", "111", "12345", "99999"};
    
    for (const string& s : tests) {
        cout << s << ": " << (canBeSegmented(s) ? "YES" : "NO") << endl;
    }
    return 0;
}

ผลลัพธ์

74325: YES  (7)(4+3)(2+5) = 7,7,7
123: YES    (1+2)(3) = 3,3
111: YES    (1)(1)(1) = 1,1,1
12345: NO
99999: YES  (9)(9)(9)(9)(9) = 9,9,9,9,9

การวิเคราะห์ "74325"

เจอ 3 เซกเมนต์ ผลรวมแต่ละอัน = 7 ✓

ความซับซ้อน

• เวลา: O(n²) - ลอง n จุดตัด × ท่อง n ตัว
• พื้นที่: O(n) - prefix sum array
• สามารถปรับปรุงเป็น O(n) ได้ด้วยการสังเกตว่า target ต้องหารผลรวมทั้งหมดลงตัว