문제 개요
n개의 객체로 이루어진 배열이 있다고 가정해 보겠습니다. 각 객체는 고유한 너비 W[i]를 가지며, 이 객체들을 다음 두 조건을 만족하도록 피라미드 형태로 쌓아야 합니다.
위쪽 층(i번째)의 총 너비는 바로 아래 층((i+1)번째)보다 작아야 합니다.
위쪽 층의 객체 수 역시 바로 아래 층보다 적어야 합니다.
예를 들어 객체의 너비가 [40, 100, 20, 30]과 같다면 결과는 2입니다. 배열을 정렬하면 [20, 30, 40, 100]이 되고, 가장 작은 값인 20을 꼭대기에 놓습니다. 그다음 층은 30과 40을 합쳐 총 너비 70, 객체 수 2개가 되어 위 조건을 모두 충족하므로 두 번째 층을 만들 수 있습니다. 마지막으로 남은 100은 하나만으로는 객체 수 조건(이전 층보다 많아야 함)을 만족하지 못해 세 번째 층을 구성할 수 없습니다. 따라서 최대 높이는 2층입니다.
해결 접근 방식: 그리디 알고리즘
이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 너비가 작은 객체를 최상단에 배치하고, 그 아래 층부터 차례대로 더 많은 객체 수와 더 큰 총 너비를 가지도록 쌓아 올리는 것입니다. 최대 층 수를 얻으려면 주어진 배열을 먼저 정렬한 뒤, 꼭대기부터 아래 방향으로 피라미드를 만들어 나갑니다.
구체적인 과정은 다음과 같습니다.
- 배열을 오름차순으로 정렬합니다.
- 정렬 후 첫 번째 요소, 즉 가장 작은 값을 찾아 꼭대기에 배치합니다.
- 그 아래 층부터는 이전 층보다 객체 수가 많고 총 너비가 커지도록 객체를 누적하며 층을 형성합니다.
- 조건을 더 이상 만족하지 못하는 순간 쌓기를 멈추고, 지금까지 완성된 층 수를 반환합니다.
C++ 구현 예제
#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
코드 설명
maxLevelPyramid 함수는 먼저 sort()로 배열을 정렬합니다. prev_w에는 직전 층의 총 너비를, count_p에는 직전 층의 객체 수를 저장하고, curr_w와 count_c는 현재 만들고 있는 층의 누적 너비와 객체 수를 추적합니다. 반복문 안에서 새 객체를 현재 층에 추가했을 때 총 너비와 객체 수가 모두 이전 층보다 크면 해당 층이 성립한 것으로 판단하고, 카운터를 초기화한 뒤 층 수(ans)를 1 증가시킵니다. 이 알고리즘은 정렬이 지배적인 비용이므로 전체 시간 복잡도는 O(n log n)이며, 입력 크기가 커져도 효율적으로 동작합니다.