[프로그래머스] 다리를 지나는 트럭

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

문제

문제

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridgelength, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truckweights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

풀이

덱을 사용해서 시뮬레이션 하듯이 풀었다. 맨 처음에 덱을 다리의 길이만큼 0으로 채워두고, 매 반복이 진행될 때마다 트럭이 들어갈 수 있는 상황(다리 위 전체 트럭무게가 다리의 최대 중량 이하 일 때)이면 트럭을 새로 넣고 아니면 0을 넣는다. 전체 다리의 무게를 계산하기 위해서 매 초가 지날 때마가 덱의 제일 끝 값을 현재 무게에서 빼주고 새로운 트럭이 들어갈 때마다 더해주는 방식을 사용했다. 다리 위에 트럭이 하나도 없을 때까지 반복하고 종료하면 최소시간을 구할 수 있다.

코드

{% raw %}
#include <string>
#include <vector>
#include <deque>
#include <iostream>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    deque<int> bridge(bridge_length);

    int totalWeight = 0;
    int idx = 0;
    while (true) {
        answer++;
        totalWeight -= bridge.back();
        bridge.pop_back();
        if (idx < truck_weights.size() && totalWeight + truck_weights[idx] <= weight) {
            totalWeight += truck_weights[idx];
            bridge.push_front(truck_weights[idx++]);
        }
        else {
            bridge.push_front(0);
        }

        if (totalWeight == 0) break;
    }

    return answer;
}
{% endraw %}