백준 #13335

내가 느낀 난이도:★★★★☆☆☆☆☆☆

---

문제 접근 방법

나는 문제를 읽어보고 큐를 쓰면 좋겠다고는 생각했는데, 방법이 막 떠오르지 않았다. 왜냐하면 입력받는 변수가 많아서 겁에 질렸기 때문이다. 그래도 해야지 뭐, 하여튼 일단 다리를 큐로 생각하고 조건이 무게와 길이인데, 무게는 그냥 total 만들어서 다리 위에 있는 무게의 총량이랑 대기 중인 차량의 무게를 더해서 다리의 최대하중보다 크지 않으면 큐에 추가하고 아니면 대기시켰다. 길이 같은 경우는 큐의 size와 다리의 길이를 비교해 여유 있을 때 차량을 추가해주었다.

//트럭리스트에서 조건에 충족하면 큐로 넣음
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
deque < pair<int,int> > bridge;
queue<int>car_list;
int car, car_weight,car_length, max_weight, max_length;
int t,total;
int main() {
	cin >> car >> max_length >> max_weight; //차량수,다리의 길이 ,다리의 최대하중
	for (int i = 0; i < car; i++) {  //각 차량의 무게를 입력받고.
		cin >> car_weight;
		car_list.push(car_weight);
	}
	while (!bridge.empty()||!car_list.empty()) { //둘다 비면 차량이 없다는것.
		t++;//사용 시간 증가
		if (!bridge.empty() && bridge.front().second == max_length) { //차량이 건넜을 때
			total -= bridge.front().first;
			bridge.pop_front();
		}
		if (!car_list.empty()&&bridge.size() < max_length && max_weight >= car_list.front() + total) {
			//차량의 리스트가 비지않음,다리에 공간이 있는지, 다리에 하중이 여유있는지
			bridge.push_back(make_pair(car_list.front(),0) );//차량의 무게,차량의 위치를묶어서 다룸
			total += car_list.front();//총 무게에 더해줌
			car_list.pop();//차량 목록에서 빼줌
		}
		for (int i = 0; i < bridge.size();i++) {
			bridge[i].second++; //다리에있는 차량의 위치를 한칸씩 옮겨줌
		}
	}
	cout << t;
}

어려웠던 점은 차량을 한 칸씩 이동하는 방법과 두 조건을 한 번에 적용시키면서 차량의 추가 여부를 결정하는 것이랑 while문의 종료 조건이다.

시간복잡도:O(n) 입력,while문