[백준] 13337 - 트럭

큐를 사용하지만 시뮬에 더 가깝다는 느낌이 들어서 simulation에 분류했다.

일단, 대기 순서를 기다린다는 것에서 유명한 문제인 은행업무 기다리기? 같은 문제처럼 이분 탐색을 하던지,

직관적으로 queue를 사용하여 시뮬레이션처럼 풀지 고민하다가 그냥 범위도 작길래 queue를 사용하였다.

1. 트럭을 다리위에 올리기 전에 트럭이 빠져 나올 수 있는지를 먼저 검사한다.

  - 트럭이 들어간 시간과 현재 지난 시간이 다리의 길이보다 클경우 pop한다

2. 1번의 검사를 마치면 큐에 문제의 조건에 만족할 수 있는 범위 내에서 큐에 넣어준다. 

3. 1, 2번의 과정을 거치지 않는다면 시간을 늘려서 순차적으로 검사한다. 

#include <iostream>
#define MAXSIZE 1001
using namespace std;
 
struct QUEUE {
    int w, t;
}q[MAXSIZE];
 
int a[MAXSIZE];
int N, W, L;
 
int calc() {
    int st, ed, pos, sum, dab;
    st = ed = sum = 0; pos = -1; dab = 1;
    q[st].t = dab; q[st++].w = a[++pos]; sum += a[pos];
    while (st != ed) {
        dab++;
        if (dab - q[ed].t >= L)    sum -= q[ed++].w;
        if (st - ed < L && sum + a[pos + 1] <= W && pos + 1 < N) {
            sum += a[++pos];
            q[st].t = dab;
            q[st++].w = a[pos];
        }
    }
    return dab;
}
 
int main(void) {
    cin >> N >> L >> W;
    for (int i = 0; i < N; i++) cin >> a[i];
    cout << calc() << endl;
    return 0;
}