[백준 13335] 트럭 (C++)

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

 

문제

---

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

 

입력

---

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a₁, a₂, ⋯ , a_n (1 ≤ a_i ≤ 10)가 주어지는데, a_i는 i번째 트럭의 무게를 나타낸다.

 

출력

---

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

 

문제 풀이

---

 

자료구조 문제.

 

트럭의 순서를 바꿀 수 없고 입력으로 주어진 순서를 그대로 사용하므로 큐를 사용하면 된다. 다리를 건너고 있는 트럭의 정보를 저장하는 큐와, 대기 중인 트럭들을 저장하는 큐 총 2개가 필요하다. 그리고 문제 조건에 맞게 1초마다 상황을 구현해주면 된다.

다리를 건너고 있는 트럭이 있다면 다리를 빠져나왔는지 확인한다. 다리에 들어간 후 w초가 경과한 후에 트럭은 다리를 빠져나올 수 있다. 다리를 빠져나왔다면 다리가 현재 견디고 있는 하중이 그만큼 줄어드므로, 현재 다리가 견디고 있는 하중을 저장할 변수 (아래 코드 bridgeWeight)이 필요하다. 그리고 다리에 들어간 후 w초 이후, 다리를 막 건넌 트럭의 무게만큼 줄어드므로 다리를 건너고 있는 트럭을 구현한 큐는 트럭이 다리에 진입한 시간과 무게를 저장한 자료구조를 저장해야 한다.

그 후, 현재 가장 첫 번째 대기 순서인 트럭의 무게와 현재 다리가 견디고 있는 하중을 합쳤을 때 최대 하중을 넘지 않는다면 해당 트럭을 다리에 진입시킬 수 있다. 대기 중인 큐에서 pop하고, 다리를 건너고 있는 트럭 큐에 push한다. 그리고 현재 하중을 업데이트한다.

마지막으로 시간 경과를 나타내는 변수를 1 증가시키면 된다. 이를 두 큐가 모두 빌 때까지 반복하면 모든 트럭이 다리를 건너는 시간을 구할 수 있다.

 

아래는 코드.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, W, L, A;
	int time = 0;
	int bridgeWeight = 0;
	cin >> N >> W >> L;
	queue<int> waitingTrucks;
	queue<pair<int, int>> inBridge;
	for (int i = 0; i < N; i++)
	{
		cin >> A;
		waitingTrucks.push(A);
	}
	while (!waitingTrucks.empty() || !inBridge.empty())
	{
		if (!inBridge.empty() && inBridge.front().second + W == time)
		{
			bridgeWeight -= inBridge.front().first;
			inBridge.pop();
		}
		if (!waitingTrucks.empty() && bridgeWeight + waitingTrucks.front() <= L)
		{
			bridgeWeight += waitingTrucks.front();
			inBridge.push(pair(waitingTrucks.front(), time));
			waitingTrucks.pop();
		}
		time++;
	}
	cout << time << "\n";
	return 0;
}