[백준/C++] 13335번: 트럭

문제

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

13335번: 트럭

---

문제 요약

강을 가로지르는 하나의 차선으로 된 다리가 있다.

 

n개의 트럭이 다리를 건너려고 한다.

 

각 트럭은 무게를 갖고, 다리 위에 있는 트럭들의 무게의 합은 다리의 최대 하중 L보다 작거나 같아야한다.

 

다리의 길이 w는 단위 길이이고, 트럭들은 단위 시간(1)에 단위 길이(1)만큼 이동할 수 있다.

 

모든 트럭이 다리를 건너는 시간을 출력한다.

---

코드

#include <iostream>
#include <queue>

using namespace std;

// 다리를 건너는 트럭 수
// 다리의 길이
// 다리의 최대 하중
int n, w, L;

queue<int> waiting_line; // i번째 대기열에 있는 트럭의 무게
queue<int> bridge; // 다리 위에 있는 i번째 트럭의 무게
queue<int> arrive; // i번째 도착한 트럭의 무게

int bridge_weight; // 현재 다리 위에 있는 트럭들의 무게 합

int main() {
	cin >> n >> w >> L;

	int run_time = 0; // 

	// 대기열에 트럭 넣기
	for (int i = 0;i < n; i++) {
		int weight;
		cin >> weight;
		waiting_line.push(weight);
	}

	// 밀어내기 위해 0 미리 넣기 (0을 삽입해서 큐의 길이 유지)
	for (int i = 0; i < w; i++) {
		bridge.push(0);
	}

	// arrive에 도착한 트럭 수가 n일 때까지
	while (n > arrive.size()) {

		// 다리 --> 도착점
		
		if (bridge.front() != 0) { // 트럭이 도착할 수 있으면
			arrive.push(bridge.front());
		}
		bridge_weight -= bridge.front();
		bridge.pop();


		// 대기열 -> 다리

		if (bridge_weight + waiting_line.front() <= L) { // 다리 위 트럭들의 무게 합 + 다음 대기 트럭 무게 <= 최대 하중
			bridge_weight += waiting_line.front();
			
			bridge.push(waiting_line.front());
			waiting_line.pop();
			waiting_line.push(0);
		}
		else {
			bridge.push(0);
		}

		run_time++;
	}

	cout << run_time;
}

---

코드 설명

코드의 핵심은 두 가지이다.

- 큐를 이용하여 트럭을 이동시킨다.

- 빈 공간에는 무게가 0인 트럭이 있다고 가정하고, 트럭이 이동하지 않는 순간에는 0이 이동한다.

(도착한 트럭 개수를 알기 위해서 arrive에는 0이 들어가지 않는다.)

 

문제를 풀기 위해서는 세 개의 큐가 필요하다.

- 다리를 건너지 못한 트럭들의 무게를 순서대로 저장하는 큐 : waiting_line

- 다리 위에 있는 트럭들의 무게를 순서대로 저장하는 큐 : bridge

- 다리를 건너간 트럭들의 무게를 순서대로 저장하는 큐 : arrive 

 

1. 먼저 트럭들의 무게들을 순서대로 입력 받아 waiting_line에 저장한다.

 

2. 다리에는 초기에 아무 트럭도 없지만, 빈 공간에 0이 있다고 가정했으므로 다리 길이만큼 0을 삽입한다.

 

3. 모든 트럭이 다리를 건널 때까지(arrive에 삽입될 때까지), 시뮬레이션을 통해 큐 간 이동을 진행한다.

 

4. 큐 간 이동은 pop, push, front를 이용해서 가장 왼쪽에 있는 트럭을 이동할 큐의 가장 오른쪽에 삽입한다.

 

< 주의할 점 >

다리위에 트럭이 하나씩 올라가고 내려올 때,

다리에서 나가는 트럭이 먼저 이동하지 않으면, 다리의 길이보다 트럭이 한 개 더 올라가는 순간이 존재한다. 

따라서, 다리에서 도착점으로 트럭이 이동하고, 그 다음 다리위로 트럭이 이동해야한다.

 

한번 루프가 진행될 때 시간을 1씩 증가시키고, 반복문이 종료될 때까지 걸린 시간을 출력한다.