백준 13335 트럭 - 큐 2개를 활용하자 c++

문제 링크: https://www.acmicpc.net/problem/13335

13335번: 트럭

큐를 이용해서 시뮬레이션을 구현하는 문제로 특별한 알고리즘은 없는 문제다.

다만 이런 시뮬레이션 문제를 처음 풀어보았기 때문에 어버버하다가 시간이 좀 걸렸다.

 

큐를 이용해야 겠다는 아이디어를 떠올린 이유는 트럭이 대기중인 '순서대로' 다리를 통과해야 되기 때문이다.

그렇기 때문에 순서를 지키면서 트럭을 이동시키기 위해서 queue를 활용해 문제를 풀어야겠다는 아이디어를 생각했다.

트럭이 대기중인 큐, 다리위에서 이동중인 트럭이 담긴 큐 2개를 만들면 된다.

 

주의할 점이 이 문제에서는 2가지가 있었는데,

 

1. 35번째 줄에 if (sum + front_truck <= weight) --> 다리와 무게가 똑같아도 트럭이 움직일 수 있다.

<=를 <로 풀면 문제가 전혀 달라짐.

 

2. 25, 33번째 줄에  if(moving_trucks.size()>0) , if(waiting_trucks.size()>0)

는 반드시 넣을 것.

저것을 안넣을 시 밑에 줄에서 빈 큐의 front() 값을 참조하게 되어 런타임 에러가 발생하게 된다.

주의해서 코딩할 것!

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int answer=0;
 
int main(void){
    int n,length,weight,t;
    cin>>n>>length>>weight;
    int answer=0;
    queue<int> waiting_trucks;
    queue<pair<int,int>> moving_trucks;
    vector<int> arrived_trucks;
    int sum=0;
    for(int i=0;i<n;i++) {
        cin >> t;
        waiting_trucks.push(t);
    }
 
    while(arrived_trucks.size()<n){
        answer++;
        int front_truck=0;
 
        if(moving_trucks.size()>0) {
            if (moving_trucks.front().second == answer) {
                int z = moving_trucks.front().first;
                arrived_trucks.push_back(z);
                sum -= z;
                moving_trucks.pop();
            }
        }
        if(waiting_trucks.size()>0) {
            front_truck = waiting_trucks.front();
            if (sum + front_truck <= weight) {
                sum += front_truck;
                waiting_trucks.pop();
                moving_trucks.push(make_pair(front_truck, answer + length));
            }
        }
 
    }
    cout<<answer;
 
}