সমস্যা বিবরণ
Kটি অণ্ডা এবং N তলার বিল্ডিং দেওয়া থাকলে, ক্রিটিক্যাল ফ্লোর F (০ থেকে N) বের করতে হয় যাতে F-এর উপরে অণ্ডা ড্রপ করলে ভাঙে, নিচে ড্রপ করলে ভাঙে না। ন্যূনতম কতটি মুভে নিশ্চিতভাবে F বের করা যায়? অণ্ডা ভাঙলে সেটি পুনরায় ব্যবহার করা যায় না।
উদাহরণ
K = 2, N = 6 → আউটপুট = 3
সমাধান পদ্ধতি
- DP + বাইনারি সার্চ অপ্টিমাইজেশন।
- dp[K][N] = K অণ্ডা এবং N তলার জন্য ন্যূনতম মুভ।
- রিকার্শন: solve(K, N) = 1 + min(max(solve(K-1, mid-1), solve(K, N-mid)))।
- বাইনারি সার্চ দিয়ে অপ্টিমাল mid বের করা হয়।
- মেমোইজেশন দিয়ে রিডান্ড্যান্ট কল এড়ানো হয়।
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 = 0, 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 = vector<vector<int>>(K + 1, vector<int>(N + 1, -1));
return solve(K, N);
}
};
int main() {
Solution ob;
cout << ob.superEggDrop(2, 6);
return 0;
}ইনপুট ও আউটপুট
ইনপুট: 2, 6
আউটপুট: 3
