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

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

13335번: 트럭

---

트럭 문제는 큐와 덱을 이용해서 해결할 수 있습니다.

 

알고리즘의 기본 틀은 아래와 같습니다. 

1. 기다리는 트럭을 모두 Queue1에 넣는다.
2. 다리 위에 있는 트럭들을 모두 앞으로 1씩 이동시킨다.
3. 다리를 건넌 트럭은, 다리 위의 트럭을 저장하는 Queue2에서 pop() 한다.
4. Queue1에서 가장 앞에 있는 트럭을 pop()하여 Queue2에 push()한다.
   (단, 다리 위에 트럭 W대가 있거나 최대 하중을 넘는 경우 트럭을 올리지 않는다.)
5. 다시 2번 과정부터 진행한다. (단, Queue1과 Queue2에 트럭이 남아있지 않다면 종료한다.)

아래는 전체 코드입니다. Queue2는 다리 위에 있는 트럭들의 무게를 계산하기 위해 편의를 위해 덱을 사용하였습니다.

#include <bits/stdc++.h>
using namespace std;

#define w first
#define p second

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

    int n, w, l;
    cin >> n >> w >> l;

    queue<int> truck;       // 다리 위에 올라가지 못한 트럭을 저장하는 queue

    for(int i = 0; i < n; i++){ // 각 트럭의 무게 입력 받음
        int w; cin >> w;
        truck.push(w);  
    }

    deque<pair<int, int>> bridge;   // 다리 위에 있는 트럭을 저장하는 queue

    int time = 0;   // 트럭들이 다리를 건너는 최단 시간
    while(!truck.empty() || !bridge.empty()){  // 모두 다리를 건널 때까지 진행
        for(int i = 0; i < bridge.size(); i++) bridge[i].p -= 1; // 다리 위 트럭 앞으로 1씩 이동

        if(!bridge.empty() && bridge.front().p == 0) // 다리를 건넌 트럭은 bridge 큐에서 pop
            bridge.pop_front();

        int weight = 0;   
        for(auto truck : bridge) weight += truck.w ;    // 다리 위에 있는 전체 트럭의 무게 계산

        if(!truck.empty() && truck.front() + weight <= l 
        && bridge.size() < w){    // 다리 위에 트럭이 올라갈 자리가 있고, 다리의 최대 하중이 남은 경우
            bridge.push_back({truck.front(), w});
            truck.pop();
        }

        time++;
    }

    cout << time;
}