Programmers 42583 다리를 지나는 트럭

08 Mar 2021 in Algorithm

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42583

나의 풀이

다리의 구조가 먼저 들어온 트럭이 먼저 나가는 FIFO 구조이기 때문에 queue를 사용하여 문제를 해결하였다.

• 1초마다 다리위에 있는 트럭들의 남은 거리를 업데이트한다. (1초에 1만큼 움직임)
• 트럭이 다리를 지나면 다리위 트럭의 총합을 지나간 트럭의 무게만큼 빼주고, 다리를 건너는 트럭에서 제외한다.
• 대기 트럭 중 맨 앞에 있는 트럭이 다리에 올라갈 수 있으면(다리가 무게를 견딜 수 있으면) 대기 트럭에 있는 트럭을 다리 위로 올린다.
• 대기 트럭과 다리를 건너는 트럭이 없을 때 까지 반복한다.

풀이 코드 : 42583 다리를 지나는 트럭

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int sum = 0;
    queue<pair<int,int>> bridge_on;
    while(true){
        answer++;
        int size = bridge_on.size();
        for(int i=0;i<size;i++){
            int len = bridge_on.front().first;
            int w = bridge_on.front().second;
            bridge_on.pop();
            if(len <= 1){
                sum -= w;
            }
            else{
                bridge_on.push(make_pair(len-1, w));
            }
        }
        if(truck_weights.size() > 0 && sum + truck_weights[0] <= weight){
            bridge_on.push(make_pair(bridge_length,truck_weights[0]));
            sum += truck_weights[0];
            truck_weights.erase(truck_weights.begin());
        }
        if(bridge_on.size() == 0 && truck_weights.size() == 0) break;
    }
    return answer;
}

int main(){
    int bridge_length = 100;
    int weight = 100;
    vector<int> truck_weights = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10};
    cout<<solution(bridge_length, weight, truck_weights);
}

채점결과