C++ / 백준 / 1092 / 배

문제

 

https://www.acmicpc.net/problem/1092

1092번: 배

문제풀이

 

크레인은 내림차순으로, 박스는 오름차순으로 정렬해서 해당 크레인만 들 수 있는 상자들을 해당 크레인에 배치한다.

그다음 크레인에서는 해당 크레인 + 이전 크레인만이 들 수 있는 개수를 공평하게 배치한다.

(이때 첫 번째에 배치한 크레인에 상자가 더 많으면 이 번에 들 수 있는 상자는 모두 두 번째 크레인이 든다)

 

내림차순으로 정렬했기 때문에, 이전 크레인들의 상자는 늘어나면 늘었지 줄어들 수는 없다.

따라서 max_cnt와 이전+해당 크레인들이 들 수 있는 상자를 나누어 공평하게 분배하면 된다.

 

상자를 나눌 때 가장 많은 상자의 개수를 구해야 하므로 상자/크레인 수의 올림과 같은 역할을 하는 수를 더해 나눈다.

(idx+1로 나누는 경우 분자에 idx를 더하면 올림과 같은 역할이 된다. ex) 7/3 = 3, 2, 2  (7+2)/3 = 3)

 

크레인이 최대로 들 수 있는 중량보다 무거운 박스가 있으면 -1을 리턴한다.

 

	for (idx = 0; idx < N; ++idx) {
		idx2 = lower_bound(box.begin(), box.end(), crane[idx + 1] + 1) - box.begin();
		sum = box.size() - idx2;
		cnt = sum - prev;
		max_cnt = max(max_cnt, (sum + idx) / (idx + 1));
		prev = sum;
	}

idx가 N-1일 때도 idx+1 부분이 작동하게 하기 위해 벡터에 미리 0을 추가하였다.

크레인을 무게 내림차순으로 탐색할 것이다.

sum은 현재 크레인을 포함하여 탐색한 크레인이 들 수 있는 상자의 총 개수,

cnt는 이번 크레인이 가장 효율적으로 들 수 있는 상자 개수,

prev는 이전 크레인이 가장 효율적으로 들 수 있는 상자 개수를 저장하는 변수이다.

 

 

0번 크레인

idx가 0이면 7보다 큰 수를 lower_bound를 이용해 현재까지 탐색한 크레인이 들 수 있는 총개수를 구한다.

cnt는 0번 크레인이 효율적으로 들 수 있는 개수를 구한다. sum에서 이전 크레인이 들 수 있는 개수를 빼서 구한다.

여기선 이전 크레인이 없으므로 3개이다.

max_cnt = max(0, 3/1)인 3이다.

 

 

1번 크레인

idx가 1이면 5보다 큰 수를 전과 마찬가지로 lower_bound를 이용해 구한다.

cnt는 sum에서 prev를 빼서 구한다.

이 경우에는 첫 번째 크레인은 그대로, 두 번째 크레인은 새로운 상자만 들면 된다.

max_cnt = max(3, 5+1/2 = 3)

 

 

2번 크레인

idx가 2이면 sum은 상자의 총 개수가 된다.

cnt는 총개수에서 이전 개수 5개를 뺀 5개가 된다.

이 경우에는 공평하게 분배를 해야 된다.

총 10개 이므로 4, 3, 3개로 나눌 수 있다. 여기서 가장 많은 상자는 4개이다. (10+2 / 3을 통해 한번에 4를 구할 수 있다.)

max_cnt = max(3, 4)로 4개가 된다.

 

이 문제에서는 구체적인 상자의 분배 현황을 구할 필요가 없으므로 이렇게 max를 이용하여 최대 개수만 구했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), M(0), idx(0), idx2(0);
	int cnt(0), prev(0), max_cnt(0), sum(0);

	cin >> N;
	vector<int>crane(N + 1);

	for (idx = 0; idx < N; ++idx) {
		cin >> crane[idx];
	}

	cin >> M;

	vector<int>box(M, 0);
	for (idx = 0; idx < M; ++idx) {
		cin >> box[idx];
	}

	sort(crane.begin(), crane.end(), greater<int>());
	sort(box.begin(), box.end());

	if (crane[0] < box.back()) {
		cout << -1;
		return 0;
	}

	for (idx = 0; idx < N; ++idx) {
		idx2 = lower_bound(box.begin(), box.end(), crane[idx + 1] + 1) - box.begin();
		sum = box.size() - idx2;
		cnt = sum - prev;
		max_cnt = max(max_cnt, (sum + idx) / (idx + 1));
		prev = sum;
	}
	cout << max_cnt;
}