[BAEKJOON] 1092 배 (C++)

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

1092번: 배

 

문제

크레인과 상자들이 존재한다.

각각의 크레인은 들 수 있는 무게 제한이 있고, 각각의 상자들에 대한 무게가 주어진다.

크레인은 동시에 움직이며 1초에 상자를 한 개 나를 수 있다.

상자를 모두 나르는데 드는 최소 시간을 구하는 문제이다.

 

접근

그리디 알고리즘은 최선의 선택을 하고 그 선택을 번복하지 않는 것이다.

이 문제에서 최선의 선택은 각각의 크레인이 움직일 때 해당 크레인이 들 수 있는 최대 무게에 가까운 상자를 옮기는 것이다.

 

첫번째 풀이

첫번째로 풀 수 있는 방법은 그냥 각 크레인에 대해서 남아있는 상자들 중 최대한 무거운 상자를 옮기게 하고 해당 상자를 erase해주는 것이다.

 while (!box.empty()) {
        cnt++;
        // 크레인 가장 큰 무게 부터
        for (int i = crane.size() - 1; i >= 0; i--) {
            // 상자 가장 큰 무게 부터
            for (int j = box.size() - 1; j >= 0; j--) {
                // 옮길 수 있으면 삭제하고 다음 크레인으로
                if (crane[i] >= box[j]) {
                    box.erase(box.begin() + j);
                    break;
                }
            }
        }
    }

이렇게 했을 때 문제점은 box의 개수가 최대 10000개인데, erase를 할 때마다 배열이 수정되므로 비효율적이다.

옮긴 박스인지 check하는 배열을 따로 선언해서 아직 남아있는 box인 경우에만 해당 박스를 옮겼다고 처리할 수도 있다. 이렇게 하면 조금 더 효율적일지도 모르겠다. 

그래도 매 실행마다 각 크레인이 최악의 경우 모든 상자를 확인해야한다. (시간복잡도를 계산하면)

 

더 효율적인 풀이

솔직히 좀 아이디어스럽기도 하고 얻어걸리긴 했지만 훨씬 효율적이다.

먼저 Crane을 정렬한다. 그리고 Box를 돌면서 각각의 박스를 옮길 수 있는 크레인 중 가장 작은 값을 찾는다.

binary search를 이용해서 자신을 들 수 있는 크레인 중 가장 작은 값의 위치를 찾고 cnt배열의 해당 위치에 값을 1 증가시킨다.

Crane이 정렬된 상태에서 i번째 Crane이 박스 a를 들 수 있다고 가정했을 때, i번째 이후에 있는 Crane들은 모두 박스 a를 들 수 있다. 

이후 cnt배열의 값을 뒤에서부터 확인하면서 sum에 업데이트 하고 sum/(지금까지 확인한 크레인의 수) 로 필요한 날짜의 평균을 구한다. 그리고 이 값들 중 최대값만큼이 모든 박스를 옮기는데 필요한 날짜이다.(나누어 떨어지는 경우가 아니면 1을 더해준다.)

예를 들어 

1 2 3 무게를 들 수 있는 크레인이 있고 박스가 2 2 2 2 총 4개 존재한다.

그러면 cnt 배열은 0 4 0 으로 완성될 것이다.

0/1 = 0

4/2  = 2

4/3  = 1 (나누어 떨어지지 않으므로 +1) -> 2

따라서 필요한 날짜는 2일이다.

 

cnt 배열에 저장된 값이 의미하는 것은, 해당 값이 기록된 크레인보다 무거운 크레인들만이 들 수 있는 박스의 개수이다.

따라서 그 크레인 앞에 몇개의 크레인이 존재하는지와 무관하게 확인한

박스의 개수/자기 포함 뒤에있는 크레인의 개수

를 구하고 그 값이 가장 큰 경우를 필요날짜로 결정하면 된다.

for (int i = N - 1; i >= 0; i--) {
		tmp = 0; sum += cnt[i];
		if (sum % (N - i) != 0) tmp++;
		tmp += (sum / (N - i));
		ans = max(ans, tmp);
	}

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"

using namespace std;

int N, M, ans, maxC, maxW;
vector<int> Crane;
vector<int> Box;
int cnt[51];
void Input() {
	int k;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> k;
		maxC = max(k, maxC);
		Crane.push_back(k);
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> k;
		maxW = max(k, maxW);
		Box.push_back(k);
	}
}

void Solve() {
	if (maxW > maxC) {
		cout << -1; return;
	}
	int start = 0;
	sort(Crane.begin(), Crane.end());
	sort(Box.begin(), Box.end());
	for (int i = 0; i < Box.size(); i++) {
		int idx = lower_bound(Crane.begin(), Crane.end(), Box[i]) - Crane.begin();
		cnt[idx]++;
	}
	int sum = 0, tmp = 0;
	for (int i = N - 1; i >= 0; i--) {
		tmp = 0; sum += cnt[i];
		if (sum % (N - i) != 0) tmp++;
		tmp += (sum / (N - i));
		ans = max(ans, tmp);
	}
	cout << ans;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "r", stdin);
	Input();
	Solve();


	return 0;
}

 

설명하기가 참 어렵다.