การทิ้งไข่ซูเปอร์ใน C++ (Super Egg Drop)

คำอธิบายปัญหา

มีไข่ K ฟอง ตึก N ชั้น มีชั้น F (0≤F≤N) ที่ไข่แตกถ้าทิ้งจากชั้น >F และไม่แตกถ้าทิ้งจากชั้น ≤F หาจำนวนการทิ้งน้อยที่สุดที่รับประกันหา F ได้

ตัวอย่าง

K=2, N=6 → Output: 3

แนวทางแก้ปัญหา: DP + Binary Search

State: dp[k][n] = จำนวนการทิ้งน้อยที่สุดสำหรับ k ฟอง n ชั้น

Recurrence:

dp[k][n] = 1 + min_{1≤x≤n} max(dp[k-1][x-1], dp[k][n-x])

• ทิ้งที่ชั้น x: แตก → เหลือ k-1 ฟอง, ต่ำกว่า x (x-1 ชั้น)
• ไม่แตก → เหลือ k ฟอง, สูงกว่า x (n-x ชั้น)
• worst case = max ของทั้งสอง
• เลือก x ให้ worst case น้อยที่สุด

ใช้ Binary Search หา x เพราะ dp[k-1][x-1] เพิ่มเมื่อ x เพิ่ม, dp[k][n-x] ลดเมื่อ x เพิ่ม

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

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

class Solution {
    vector<vector<int>> dp;
    
    int solve(int K, int N) {
        if(N <= 1) return N;
        if(K == 1) return N;
        if(dp[K][N] != -1) return dp[K][N];
        
        int ret = N, low = 1, high = N;
        while(low <= high) {
            int mid = low + (high-low)/2;
            int left = 1 + solve(K-1, mid-1);
            int right = 1 + solve(K, N-mid);
            ret = min(ret, max(left, right));
            if(left == right) break;
            if(left < right) low = mid+1;
            else high = mid-1;
        }
        return dp[K][N] = ret;
    }
    
public:
    int superEggDrop(int K, int N) {
        dp.assign(K+1, vector<int>(N+1, -1));
        return solve(K, N);
    }
};

ความซับซ้อน

• เวลา: O(K × N log N) ด้วย binary search
• พื้นที่: O(K × N)
• มีวิธี O(K × N log N) หรือ O(K log N) ด้วยการกลับมอง: dp[m][k] = ชั้นสูงสุดที่ทดสอบได้ด้วย m moves k eggs