이 문제에서는 각 요소가 상자 더미(각 단위 높이)를 나타내는 배열 arr[]이 제공됩니다. 우리의 임무는 제거할 상자의 수를 찾는 것입니다. .
사람은 상자 더미의 높이에서 배열의 인덱스 0에 서 있고 배열의 끝으로 이동해야 합니다. 한 더미에서 다음 더미로 이동하는 조건은 다음 더미로 점프하는 것입니다.
점프는 다음 더미의 높이가 같거나 낮은 경우에만 가능합니다. 다음 더미의 높이가 더 높으면 높이가 같아질 때까지 다음 더미에서 상자를 제거해야 합니다. 첫 번째 상자에서 마지막 상자로 이동하는 동안 제거될 총 상자 수를 찾아야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input : arr[] = {5, 7, 3 , 1, 2}
Output : 3 설명
처음에는 키가 5입니다.
1단계 − 높이가 7인 두 번째 위치로 이동하려면 2개의 상자를 제거해야 합니다.
2단계 − 높이 3의 세 번째 위치로 이동하기 위해 상자가 제거되지 않습니다.
3단계 − 높이 1의 다음 위치로 이동하기 위해 상자가 제거되지 않습니다.
4단계 − 높이 2의 다음 위치로 이동하기 위해 하나의 상자가 제거됩니다. 이렇게 하면 제거된 상자의 수가 3이 됩니다.
솔루션 접근 방식
문제에 대한 간단한 해결책은 배열을 처음부터 끝까지 순회하고 다음 요소가 현재 요소보다 큰지 확인하는 것입니다. 그렇다면 boxesRemoved에 차이점을 추가하세요. 제거될 총 상자 수를 보유하는 변수입니다. 마침내 boxesRemoved가 반환됩니다. .
예시
솔루션 작동을 설명하는 프로그램
#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