[스택/큐] 다리를 지나는 트럭

|| 문제설명 ||

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

이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성해라.

  • bridge_length : 다리 길이
  • weight : 다리가 견딜 수 있는 무게
  • truck_weights : 트럭별 무게
_ bridge_length : 1 이상 10,000 이하
_ weight : 1 이상 10,000 이하
_ truck_weights의 길이 : 1 이상 10,000 이하
_ 모든 트럭의 무게 : 1 이상 weight 이하

|| 문제해결방법 ||


|| 코드 ||

[2020.09.30] 성공
#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, w= 0, in = 0, out = 0;
    queue<int> q;
    while(out < truck_weights.size()) {
        if(in < truck_weights.size()) {
            if(w + truck_weights[in] <= weight) {
                q.push(truck_weights[in]);
                w += truck_weights[in];
                in++;
            }
            else q.push(0);
        }
        else q.push(0);
            
        if(q.size() == bridge_length) {
            w -= q.front();
            if(q.front() > 0) out++;
            q.pop();
        }      
        answer++;
    }
    
    return answer + 1;
}


[2021.01.16]

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

using namespace std;

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

    while(1) {
        if(bridge.size() == bridge_length) {
            if(bridge.front() == -1) break;
            total_weight -= bridge.front();
            bridge.pop();
        }
        if(top < truck_weights.size()) {
            if(total_weight + truck_weights[top] <= weight) {
                total_weight += truck_weights[top];
                bridge.push(truck_weights[top++]);
            }
            else bridge.push(0);
        }
        else bridge.push(-1);
        answer++;
    }
    return answer;
}

좋은 웹페이지 즐겨찾기