[BOJ/백준 13335/C++] 트럭

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

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개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

- 시간제한 : 1초

- 메모리제한 : 512MB

 

[문제 풀이]

문제를 간단하게 해석하자면, 일렬로 무게가 다른 트럭들이 다리를 지나간다. 트럭들을 1초동안 한칸을 움직인다고 생각하면되고 다리를 다 건너기 위해서는 w칸 만큼 지나야 한다고 생각하면된다.

 

필자는 큐(queue)를 이용하여 큐에 {트럭의 무게, 진입한 초}를 큐에 집어넣는 방식을 이용하였다.

 

• 다음 트럭이 다리를 건널 수 있는가?
  • 없다면 : 큐에 들어 있는 트럭들을 다음 트럭이 다리에 진입할 수 있을 때까지 시간을 진행시킨다. 다리를 건너 트럭에 대해서는 큐에서 제외시킨다.
  • 있다면 : 큐에 넣는다.
• 모든 트럭에 대해 확인했으면 큐에 남아있는 트럭이 있다면 큐가 빌때까지 시간을 진행시킨다. 

이때 큐에서 트럭이 빠지는 조건은 (현재시간 - 큐에 들어간 시간) >= w 인 경우에 큐에서 빠지게 된다.

 

[소스 코드]

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

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int n, w, l;
vector<int> truck;

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

	cin >> n >> w >> l;

	for (int i = 0; i < n; i++)
	{
		int tmp;
		cin >> tmp;
		truck.push_back(tmp);
	}

	queue<pii> q;
	int sum = 0;
	int time = 1;
	for (int i = 0; i < n; i++)
	{
		while (!q.empty() && time - q.front().second >= w)
		{
			sum -= q.front().first;
			q.pop();
		}


		if (sum + truck[i] <= l)
		{
			q.push({ truck[i], time });
			sum += truck[i];
			time++;
		}
		else
		{
			while (sum + truck[i] > l)
			{
				while (time - q.front().second < w) time++;
				sum -= q.front().first;
				q.pop();
			}
			sum += truck[i];
			q.push({ truck[i], time });
			time++;
		}
	}
	while (!q.empty())
	{
		if (time - q.front().second >= w) {
			q.pop(); 
			if (q.empty()) break;
		}
		time++;
	}
	cout << time;
}

굳