백준 13335번: 트럭

백준 13335번: 트럭

13335번: 트럭

 

시뮬레이션 문제로 트럭의 순서를 바꾸지 않고 다리길이만큼 무게를 초과하지 않고 트럭을 끝으로 보내는 문제이다. 나는 큐를 사용하여문제를 풀었다. 큐에 지나갈 수 있는 트럭을 넣고 하중을 초과하지 않으면 그 다음 트럭을 계속 넣는다. 초과한다면 0을 넣어 큐 내부를 계속 움직이게 해주었다. 큐의 사이즈가 w를 초과하면 큐에 있는 내용들을 하나 씩 pop을 하여 트럭 혹은 0값들을 제거한다. 트럭이 제거될때마다 카운트를 1씩 증가 시켜줘 다리를 건넌 트럭의 수를 세어주어 마지막 트럭이 pop되었을 때 반복문을 종료할 수 있도록 만들어주었다. 무게 같은 경우는 큐에 들어가는 트럭들의 무게를 더해주고 큐에서 나올때 그트럭의 값을 빼도록 하여 다리의 무게에 초과되지 않게 트럭들을 큐에 넣을 수 있게했다. 마지막으로 모든 트럭이 다리를 건널때까지 시간 카운트를 해주었다.

 

#include<iostream>
#include<queue>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int truck[1000];
    queue<int> q;
    int n, w, l;
    int sum = 0;
    cin >> n >> w >> l;
    for(int i = 0; i < n; i++){
        cin >> truck[i];
    }
    int index = 0;
    int cnt = 0;
    int pp = 0;
    while(pp != n){
        if(q.size() >= w){
            int tmp = q.front();
            q.pop();
            sum -= tmp;
            if(tmp != 0)
                pp += 1;
        }
        if(truck[index]+sum <= l){
            q.push(truck[index]);
            sum += truck[index];
            index += 1;
        }
        else{
            q.push(0);
        }
        cnt += 1;
    }
    cout << cnt;
    return 0;
}