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

문제

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

출력

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

예제 입출력

• 예제 입력 1

4 2 10
7 4 5 6

• 예제 출력 1

8

• 예제 입력 2

1 100 100
10

• 예제 출력 2

101

• 예제 입력 3

10 100 100
10 10 10 10 10 10 10 10 10 10

• 예제 출력 3

110

Solution

#include <bits/stdc++.h>

using namespace std;

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

    deque<int> bridgeDq;
    deque<int> Que;
    int N, W, L;
    int time = 0;
    int nowWeight = 0;
    int count = 0;
    cin >> N >> W >> L;
    
    for(int i = 0; i < W; i++){
        bridgeDq.push_back(0);
    }

    for(int i = 0; i < N; i++){
        int data; cin >> data;
        Que.push_back(data);
    }

    while(count != N){
        if(bridgeDq.front() != 0){
            nowWeight -= bridgeDq.front();
            count++;
        }
        bridgeDq.pop_front();

        if(nowWeight < L){
            if(!Que.empty() && nowWeight + Que.front() <= L){
                nowWeight += Que.front();
                bridgeDq.push_back(Que.front());
                Que.pop_front();
            } else {
                bridgeDq.push_back(0);
            }
        } else {
            bridgeDq.push_back(0);
        }
        time++;
    }

    cout << time << '\n';
}

처음에는 간단하게 실제 다리를 하나 놓았다 생각하고 두 개의 Deque를 통해 무작정 돌려보는 형태를 띄었다.

for(int i = 0; i < W; i++){
    bridgeDq.push_back(0);
}

for(int i = 0; i < N; i++){
    int data; cin >> data;
    Que.push_back(data);
}

다리는 우선 0으로 가득 채운다. 그리고 기존의 정보들을 모두 deque에 저장한다.

while(count != N){
    if(bridgeDq.front() != 0){
        nowWeight -= bridgeDq.front();
        count++;
    }
    bridgeDq.pop_front();

    if(nowWeight < L){
        if(!Que.empty() && nowWeight + Que.front() <= L){
            nowWeight += Que.front();
            bridgeDq.push_back(Que.front());
            Que.pop_front();
        } else {
            bridgeDq.push_back(0);
        }
    } else {
        bridgeDq.push_back(0);
    }
    time++;
}

1. 먼저 다리의 front를 확인 후 0이 아니라면 현재 중량에서 그 값을 제하고 현재까지 건넌 트럭의 갯수를 세는 변수 count에 1을 더한다.
2. 덱 front를 pop한다.
3. 만약 현재 중량이 L보다 작다면 대기중인 트럭이 존재하고 맨 앞의 트럭이 현재 중량과 더했을 때 L보다 작거나 같다면 현재 중량을 갱신하고 다리 deque에 해당 값을 push후 대기 queue는 pop한다. 그게 아니라면 그냥 0을 집어넣는다.

이 사이클을 계속 반복한다.