[백준 BOJ/C++] 1092 배

1092번: 배

전형적인 그리디 알고리즘 문제이지만 시간 초과 가능성을 고려해야 한다.
특별한 복잡한 스킬이 필요하진 않지만 그리드 적인 접근 방식을 연습하기 좋은 문제다.

 

N대의 크레인에 M개의 박스를 최소 횟수로 옮기는 문제다. 각 크레인에는 무게 제한이 있어서 제한 내의 무게를 가진 박스만 옮길 수 있다. 크레인에 박스를 효율적으로 배분해서 최소 몇 회 만에 옮길 수 있는지 찾아야 한다.

 

 

---

 

문제의 포인트

1. 그리디 알고리즘
2. 시간초과를 피하는 방법

 

그리디 알고리즘

Greedy Algorithm은 사실 특별한 기술이나 전형적인 틀이 있는 유형은 아니다.
어찌보면 그만큼 발견이나 아이디어가 중요다고 할 수 있다.

 

 

그래도 그리드 알고리즘 문제를 여럿 풀다보면 어느정도 접근 방법에 대한 감을 기를 수 있다.
숫자의 대소 관계가 중요하다면 우선 정렬을 하고 순차적으로 선택해가는 방식을 고려해보면 좋다.

 

 

이 문제도 마찬가지로 정렬을 통해 큰 숫자부터 배분해나가면 생각보다 쉽게 해결 방법을 찾을 수 있다.
아래와 같은 순서로 풀어보았다.

 

 

1. 크레인과 박스를 모두 내림차순으로 정렬시킨다.
2. 하나씩 크레인과 박스를 선택하면서 크레인에 넣을 박스를 고른다.
3. 모든 박스를 옮길 때까지 반복하고 반복한 횟수를 출력한다.

 

크레인보다 무거운 박스가 존재해 모든 박스를 옮길 수 없는 경우에 대한 처리나 크레인이 박스보다 많은 케이스 등 몇가지 사소한 실수를 제외하면 풀기 쉽다고 볼 수 있는데 M * N의 2중 loop를 돌아야 하는 점 때문에 시간초과가 발생하기 쉽다.
아마도 그래서 정답비율이 낮은편인것 같다.

 

 

시간 제한

박스를 옮길 때 이미 옮긴 박스의 index까지 다시 확인해야 한다면 시간초과가 발생할 가능성이 높다.
C++ 보다 C언어가 익숙해서 무식하게 아무생각 없이 크레인과 박스를 모두 배열로 만들고 시작하니 이미 옮긴 박스의 index를 아예 참조도 하지 않도록 하기에는 간단하지 않았다.

 

아무리 내림차순 정렬이 되어있더라도 박스가 반드시 순차적으로 빠지는 것이 아니기 때문에 당연히 배열에는 구멍이 뚫린 듯 듬성 듬성 옮겨야 할 박스가 남아있을 수 있다.

 

 

배열 형태로 이를 처리하는 방법을 고민하느니 vector를 써서 이미 옮긴 박스 item을 제거시켜 버리는 것이 맞을 것 같았다.
역시 이와 같이 처리하면 시간초과 없이 문제를 풀 수 있었다.

 

 

---

 

전체 Code

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

using namespace std;

int N, M;
int W[50 + 10];
vector<int> B;

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
    
    int i, j, b, cnt = 0;
    
	cin >> N;

	for (i = 0; i < N; i++) {
		cin >> W[i];
	}

	cin >> M;

	for (i = 0; i < M; i++) {
		cin >> b;
		B.push_back(b);
	}

	sort(W, W + N, greater<int>());
	sort(B.begin(), B.end(), greater<int>());

	if (W[0] < B[0]) {
		cout << "-1\n";
		return 0;
	}

	while (!B.empty()) {
		cnt++;

		for (i = 0; i < N; i++) {
			for (j = 0; j < B.size(); j++) {
				if (W[i] >= B[j]) {
					B.erase(B.begin() + j);
					break;
				}
			}
		}
	}

	cout << cnt << "\n";

	return 0;
}