programmers 다리를 지나는 트럭

programmers

level2 다리를 지나는 트럭

문제 설명

위 이미지를 클릭하시면 해당 문제로 이동합니다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, now = 0;
    queue <pair<int, int>> on_bridge;
    int cnt = 0;
    while(1){
        answer++;
        if(!on_bridge.empty() && answer - on_bridge.front().second >= bridge_length){
            now-=on_bridge.front().first;
            on_bridge.pop();
        }
        if(now + truck_weights[cnt] <= weight){
            on_bridge.push({truck_weights[cnt], answer});
            now += truck_weights[cnt];
            cnt++;
        }
        else answer=on_bridge.front().second + bridge_length - 1;

        if(cnt == size(truck_weights)) {answer+=bridge_length; break;}
    }
    return answer;
}

해결 과정

1초씩 더해줘가며 다리가 수용할 수 있는 최대 하중을 초과하지 않을 때까지 트럭을 다리 queue에 push해주었습니다.
다음 트럭을 올려서 최대 하중을 초과하는 경우에는 가장 처음의 트럭이 다리에서 내리는 시점까지 skip 해서 불필요한 반복을 줄였습니다.
마지막 트럭까지 다리에 올라간 경우에는 바로 다리의 길이만큼 answer에 추가해주고 종료했습니다.

• 요약
  1. queue 이용
  2. 최대하중 초과시 가능한 시점까지 skip
  3. 마지막 트럭 이동시 종료