C++의 주어진 객체 배열에서 최대 높이 피라미드 찾기

n개의 객체로 구성된 배열이 있다고 가정합니다. 각 객체의 너비는 W[i]입니다. 다음과 같이 피라미드 방식으로 정렬해야 합니다.

• i번째 너비가 (i + 1)번째보다 작습니다.

• i번째 객체의 총 개수가 (i + 1)번째보다 작습니다.

예를 들어 가중치가 [40, 100, 20, 30]과 같으면 출력은 2가 됩니다. 따라서 최상위 수준은 30이고 하위 수준은 20, 40 및 100입니다.

이를 해결하기 위해 greedy 접근 방식을 사용합니다. 아이디어는 너비가 낮은 개체를 맨 위에 놓고 다음 개체를 바로 아래 수준에 배치하는 식으로 사용하는 것입니다. 최대 레벨 수를 얻으려면 주어진 배열을 정렬하고 위에서 아래로 피라미드를 형성하십시오.

그런 다음 정렬 후 배열의 첫 번째 요소와 같은 배열의 가장 작은 요소를 찾아 맨 위에 놓습니다. 그런 다음 더 많은 수의 개체와 더 큰 너비로 그 아래에 레벨을 구축해 보십시오.

예시

#include <iostream>
#include <algorithm>
using namespace std;
int maxLevelPyramid(int objects[], int n) {
   sort(objects, objects + n);
   int ans = 1;
   int prev_w = objects[0];
   int count_p = 1;
   int count_c = 0;
   int curr_w = 0;
   for (int i=1; i<n; i++){
      curr_w += objects[i];
      count_c++;
      if (curr_w > prev_w && count_c > count_p){
         prev_w = curr_w;
         count_p = count_c;
         count_c = curr_w = 0;
         ans++;
      }
   }
   return ans;
}
int main() {
   int boxes[] = {40, 100, 20, 30};
   int n = sizeof(boxes)/sizeof(boxes[0]);
   cout << "Max level of pyramid: " << maxLevelPyramid(boxes, n);
}

출력

Max level of pyramid: 2