[백준 13335] 트럭 C++

문제

백준 13335 트럭 C++

13335번: 트럭

풀이

트럭이 순차적으로 다리를 건너므로(FIFO) 큐를 이용한다.

3단계로 나눠서 풀면 편하다.

다리 위로 안 올라간 트럭들의 Queue와

다리 위에서 움직이고 있는 트럭 Queue

다리 위에서 움직이고 있는 트럭의 거리를 1증가시켜줄 임시 Queue 3개를 선언한다.

 

1단계 - 이미 다리 위에 있는 트럭들을 모두 1칸 앞으로 이동시킨다.

1-1 : 이 때 트럭이 다리를 건넜으면, 다리 queue에서 빼준다.

2단계 - 새 트럭을 올릴 수 있으면 올린다.

2-1 : 트럭을 올렸다면 대기 Queue에서 빼준다.

3단계 - 대기 Queue와 다리 Queue를 검사하여 모두 비었다면 트럭이 전부 건넌 것이므로 루프를 종료

그 후 time을 출력한다.

소스 코드

#include<iostream>
#include<queue>
using namespace std;
 
// 아직 다리 안 올라간 트럭들
queue<int> waitTruckQueue;
// 무게, 간 거리
queue<pair<int, int>> goingTruckQueue;
// 임시로 1 더해주는 큐
queue<pair<int, int>> tempQueue;
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    int w;
    int L;
 
    cin >> n >> w >> L;
 
    for (int i = 0; i < n; i++)
    {
        int weight;
        cin >> weight;
        waitTruckQueue.push(weight);
    }
 
    int time = 0;
    int weightSumOnBridge = 0;
    while (1)
    {
        time += 1;
        // 1. 다리 위 트럭들 1칸 전진, 도착하면 Pop
        while (goingTruckQueue.empty() == false)
        {
            int weight = goingTruckQueue.front().first;
            int distance = goingTruckQueue.front().second;
            goingTruckQueue.pop();
            tempQueue.push(make_pair(weight, distance));
        }
 
        while (tempQueue.empty() == false)
        {
            int weight = tempQueue.front().first;
            int distance = tempQueue.front().second;
            distance += 1;
            tempQueue.pop();
            if (distance < w)
            {
                goingTruckQueue.push(make_pair(weight, distance));
            }
            else
            {
                weightSumOnBridge -= weight;
            }
        }
        // 2. 대기 트럭 갈 수 있으면 전진 후 큐에 Push
        if (waitTruckQueue.empty() == false)
        {
            int nextTruckWeight = waitTruckQueue.front();
            if (nextTruckWeight + weightSumOnBridge <= L)
            {
                goingTruckQueue.push(make_pair(nextTruckWeight, 0));
                weightSumOnBridge += nextTruckWeight;
                waitTruckQueue.pop();
            }
        }
        // 3. 다 지나갔는지 확인
        if (waitTruckQueue.empty() && goingTruckQueue.empty())
            break;
    }
 
    cout << time;
    return 0;
}