백준 13335 트럭 (C++)

13335번: 트럭

큐를 이용한 구현 문제이다. 다리의 선입선출하는 모습을 큐로 대입하여 문제를 풀어보았다. sum은 현재 다리 위의 무게의 합을, arrival은 다리를 건넌 트럭의 개수를 나타낸다. 큐를 다리로 대입한다면q.size는 다리 위의 트럭의 개수를 나타내므로 q.size() == w이면 다리에 자리가 없다는 것을 의미하므로 자리를 만들기 위해 q.pop을 해준다. 그 후 무게를 비교하여 다음 트럭을 큐에 넣어준다. 만약 이전 무게와 트럭 무게의 합이 최대하증을 넘어가게 되면 트럭이 아닌 허수 -1을 큐에 추가해준다. 이는 먼저 올라가있던 트럭이 다리 끝에 도달했는지 알기 위해 추가해주는 것이고 나중에 q.pop을 할 때 -1일 경우 arrival을 추가해주지 않는다. 반복문이 돌 때마다 카운트를 해준 후 이를 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다.

#include <iostream>
#include <queue>

using namespace std;

int n, w, L, result = 0;
int A[1000];

void solution() {
    queue<int> q;
    int sum = 0, arrival = 0, now = 0;

    while (arrival != n) {
        if (q.size() == w) {
            int end = q.front();
            q.pop();

            if (end != -1) {
                sum -= end;
                arrival++;
            }
        }

        int start = A[now];

        if (q.size() < w && sum + start <= L) {
            q.push(start);
            sum += start;
            now++;
        }
        else {
            q.push(-1);
        }

        result++;
    }

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> w >> L;

    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}