এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে [] যেখানে প্রতিটি উপাদান একটি গাদা বাক্সের প্রতিনিধিত্ব করে (প্রতিটি ইউনিট উচ্চতা)। আমাদের কাজ হল বক্সের সংখ্যা বের করা .
ব্যক্তিটি বাক্সের স্তূপের উচ্চতায় অ্যারের সূচক 0 এ দাঁড়িয়ে আছে এবং তাকে অ্যারের শেষে যেতে হবে। এক স্তূপ থেকে অন্য স্তূপে যাওয়ার শর্ত হল পরেরটিতে ঝাঁপ দেওয়া।
লাফানো তখনই সম্ভব যখন পরবর্তী পাইলটি একই উচ্চতায় থাকে বা এর চেয়ে কম উচ্চতায় থাকে। পরবর্তী স্তূপের উচ্চতা বেশি হলে উচ্চতা সমান না হওয়া পর্যন্ত ব্যক্তিকে পরবর্তী স্তূপ থেকে বাক্সগুলি সরিয়ে ফেলতে হবে। প্রথম বাক্স থেকে শেষের দিকে যাওয়ার সময় আমাদের মোট কতগুলি বাক্স সরানো হবে তা খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : arr[] = {5, 7, 3 , 1, 2}
Output : 3 ব্যাখ্যা
প্রাথমিকভাবে, ব্যক্তির উচ্চতা 5।
ধাপ 1 − 7টি উচ্চতা বিশিষ্ট দ্বিতীয় অবস্থানে যেতে, ব্যক্তিকে 2টি বাক্স সরাতে হবে৷
ধাপ 2 − 3 উচ্চতায় তৃতীয় অবস্থানে যেতে, কোনো বাক্স সরানো হয় না।
ধাপ 3 − 1 উচ্চতায় পরবর্তী অবস্থানে যেতে, কোনো বাক্স সরানো হয় না।
পদক্ষেপ 4৷ − 2 উচ্চতায় পরবর্তী অবস্থানে যেতে, একটি বাক্স সরানো হয়। এটি সরানো বাক্সের সংখ্যা 3 এর সমান করে তোলে।
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল শুরু থেকে শেষ পর্যন্ত অ্যারেটি অতিক্রম করা এবং পরবর্তী উপাদানটি বর্তমানের থেকে বড় কিনা তা পরীক্ষা করা। যদি হ্যাঁ, তাহলে বক্সগুলি সরানো-এ তাদের পার্থক্য যোগ করুন পরিবর্তনশীল যা বক্সের মোট সংখ্যা ধারণ করে যা সরানো হবে। শেষ পর্যন্ত, আমরা বক্সগুলি সরানো ফেরত দেব .
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findBoxesRemoved(int arr[], int n){
int boxesRemoved = 0;
for (int i = 0; i < n-1; i++) {
if (arr[i] < arr[i+1])
boxesRemoved += (arr[i+1] - arr[i]);
}
return boxesRemoved;
}
int main(){
int arr[] = { 5, 7, 3 , 1, 2, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The total number of boxes to be removed to reach the end is "<<findBoxesRemoved(arr, n);
return 0;
} আউটপুট
The total number of boxes to be removed to reach the end is 7
