[백준/c++] 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 문제로 재활치료를 하려고 했는데 의외로 오래걸려버렸다. 코테는 감 유지가 제일 중요하다...

일단 문제로 돌아가보면, 여러가지 조건으로 표현할 수 있겠지만 가장 중요한 조건은 어느 시점 시간이 지나가면 트럭이 계속해서 통과를 하게 된다.

본인은 두개의 큐를 만들어서 일정 시간(다리의 길이 시간 만큼)이 지나가게 되면 계속해서 빠져 나가는 형태로 만들었다. 중간에 하중때문에 들어가지 못하는 트럭은 0으로 계속해서 집어넣어 문제를 해결했다. 변수명이 마음에 들지 않는다.

1. 두 개의 큐를 사용해서 문제를 해결

2. 조건은 일정 시간이 지났을 때부터는 첫번째 큐에서 계속해서 넣으면서(하중이 허락하면), 두번째 큐에서는 일정 시간(다리의 길이)만큼 지났으면 계속해서 빼주기!

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

int n,w,l,t;

queue<int> q,bridge;

int main(){
	
	cin >> n >> w >> l;
	
	for(int i = 0; i < n; i++){
		cin >> t; q.push(t);
	}
	
	int time = 0;
	
	while(!q.empty()){
		
		time++;
		int weight = q.front();
		
		if(time <= w){
			// 하중 ok?
			if(l - weight < 0){
				bridge.push(0);
			}
			else{
				l -= weight;
				q.pop();
				bridge.push(weight);
			}
		}
		else if(time > w){
			
			int ww = bridge.front();
			bridge.pop();
			l += ww;
			
			if(l - weight < 0){
				bridge.push(0);
			}
			else{
				l -= weight;
				q.pop();
				bridge.push(weight);
			}
		}			
	}
		
	time += w;
	
	cout << time;
	
	return 0;
}