소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\n"
#define INF 987654321

using namespace std;

int n;                  // 점원 수
int b;                  // 선반 높이
vector<int> heights;	// 점원들의 키 벡터
vector<int> partialSum; // 점원들 키의 부분합
int curHeight;          // 현재 탑의 높이
int minHeight;          // B이상의 탑의 최소 높이

void input() {
	// 전역 변수 초기화
	curHeight = 0;
	minHeight = INF;

	cin >> n >> b;
	heights = vector<int>(n);

	for (int i = 0; i < n; ++i) {
		cin >> heights[i];
	}

	sort(heights.begin(), heights.end(), greater<int>()); // 내림차순 정렬
	partialSum = vector<int>(n);
	partialSum[0] = heights[0];

	for (int i = 1; i < n; ++i) {
		partialSum[i] = partialSum[i - 1] + heights[i];
	}
}

void findMinHeight(int curPeople, int start, int targetPeople) {
	if (curPeople == targetPeople) {
		if (curHeight >= b && minHeight > curHeight) {
			minHeight = curHeight;
		}

		return;
	}

	// 더 뽑아야 하는 수보다 남은 수가 적을 경우 반환 (커팅1)
	if (n - start < targetPeople - curPeople) return; 

	// 더 뽑아야 하는 수만큼 큰 수로만 뽑아 선반 길이에 반영해도 b보다 작은 경우 반환 (커팅2)
	if (start != 0 && \
		start + targetPeople - curPeople - 1 < n && \
		curHeight + partialSum[start + targetPeople - curPeople - 1] - partialSum[start - 1] < b) {
		return;
	}

	for (int i = start; i < n; ++i) {
		curHeight += heights[i];

		findMinHeight(curPeople + 1, i + 1, targetPeople);

		curHeight -= heights[i];
	}
}

void solve() {
	input();

	for (int people = 1; people <= n; ++people) {
		// 해당 인원으로 구성할 수 있는 가장 큰 선반을 만들어도 b보다 높이가 작은 경우 continue
		if (partialSum[people - 1] < b) {
			continue;
		}

		curHeight = 0;
		findMinHeight(0, 0, people);
	}

	cout << minHeight - b << endl;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	freopen("sample_input.txt", "r", stdin);

	int TC;
	cin >> TC;

	for (int tc = 1; tc <= TC; ++tc) {
		cout << "#" << tc << " ";
		solve();
	}

	return 0;
}

해설

조건에 맞는 경우(선반 길이가 b 이상일 것 + 앞선 조건을 만족하며 최소 길이일 것)를 탐색하기 위한 백트래킹
+++
시간초과 방지를 위한 커팅
(더 뽑아야 하는 수가 k인데 남은 수가 k 미만인 경우 커팅 + 남은 수가 k이상이더라도 더 뽑아봤자 b 미만인 경우 커팅)