백준 1092 배

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 크레인을 이용해 박스를 옮기는데 걸리는 최소 시간을 구하는 문제입니다. 각 크레인은 무게 제한이 있어 더 무거운 박스는 옮길 수 없습니다.

 

저는 리스트를 이용해 크레인이 옮길 수 있는 박스들을 제거해 가며 문제를 풀었습니다. 박스가 저장된 리스트와 크레인이 저장된 배열을 각각 sort 시킨뒤 가장 무거운 박스를 해당 크레인이 옮길 수 있는지를 검사하고 옮길 수 없다면 그다음으로 무거운 박스를 옮길 수 있는지를 검사 하였습니다. 

 

만약 어떤 크레인이 리스트의 끝까지 갔는데도 어떠한 박스도 옮길 수 없다면 그 크레인의 뒤에 있는(그 크레인보다 무게제한이 더작은) 크레인들을 포함하여 전체 크레인에서 빼주어서 필요없는 검사를 줄였습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <algorithm>
#include <list>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N;
	cin >> N;
	int limit[N];
	int time = 0;
	bool flag;
	
	for(int i = 0; i < N; i++)
		cin >>limit[i];
	
	sort(limit, limit+N, greater<int>());
	
	int M;
	cin >> M;
	
	list<int> l;
	
	for(int i = 0; i < M; i++) {
		int x;
		cin >> x;
		l.push_back(x);
	}
	
	l.sort(greater<int>());
	
	if(l.front() > limit[0])  //가장 무거운 크레인이 가장 무거운걸 들 수 없으면 -1 출력 
			time= -1;
			
		
	else {
		while(!l.empty()) { //박스가 다 옮겨질때 까지 
			flag = true;
			for(int i = 0; i < N; i++) {
				if(l.empty()) //박스가 비었으면 break 
					break;
				
				if(l.front() <= limit[i])  // 가장 무거운 박스를 크레인이 옮길 수 있으면 박스 옮기기 
					l.pop_front();
				
				else  {
					for(auto it = l.begin(); it != l.end(); it++) // 가장 무거운 박스를 못 옮길경우 다음 박스를 옮길 수 있는지 검사 
						if(*it <= limit[i]) {
							l.erase(it);
							flag = false;
							break;
						}
					
					if(flag) // 아무박스도 못옮겨서 쓸수가 없는 크레인은 제거
						N = N - (N - i);
				}	
				}
			time++;
		}
	}
	 
	cout<<time;
	return 0; 
}