[알고리즘] 트럭

구현 방식

• 현재 다리에 있는 무게가 지금 추가할려는 트럭의 무게를 추가할 수 없는 상태라면, 시간이 흐르게끔 대기를 해야하므로, 큐에다가 넣고 빼고 만 하면 안된다.
• 추가할 수 없는 상태라면, 무게가 0인 가짜 트럭을 보내도록한다.
• 이걸로 얻을 수 있는 장점은 큐에 넣는만큼 시간이 흐른다는 것이다.
• 미리 큐에 브릿지 길이만큼 0(가짜트럭) 을 추가해줘서, 사이즈 체크를 하지않고, 앞에 트럭을 계속 보낼수있도록 만든다.

코드

• 최종 코드는 아래와 같다.

void solution(int w, int L, queue<int>& trucks)
{
	queue<int> q;
	for (int i = 0; i < w; i++) q.push(0); // 0으로 브릿지 길이만큼 채운다.
	int weight = 0;
	int counter = 0;
	while (!trucks.empty())
	{
		int truck = trucks.front();
		// 브릿지의 가장 앞 트럭 보내기
		weight -= q.front();
		q.pop();
		counter++;
		if (weight + truck <= L)
		{
			q.push(truck);
			weight += truck;
			trucks.pop();
		}
		else q.push(0);

	}
	// 브릿지에 남아있는 트럭 보내기
	while (!q.empty())
	{
		counter++;
		q.pop();
	}


	cout << counter ;
}