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

안녕하세요, 루피입니다.

 

오늘은 프로그래머스 다리를 지나는 트럭문제 풀이를 정리 해보려합니다.

 

바로 시작합니다.

---

문제 풀이

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 0;
    int current_weight = 0;
    
    queue<int> bridge;
    
    for (int i = 0; i < truck_weights.size(); i++) {
        int next_truck = truck_weights[i];
        
        while (true) {
            time++; 

            if (bridge.size() == bridge_length) {
                current_weight -= bridge.front();
                bridge.pop();
            }

            if (current_weight + next_truck <= weight) {
                bridge.push(next_truck);
                current_weight += next_truck;
                break;
            } else {
                bridge.push(0);
            }
        }
    }

    return time + bridge_length;
}

이번 문제의 핵심은 다리라는 큐를 만들어 내는 것이라고 생각합니다. 

1. bridge 라는 큐를 만듭니다.
2. 대기 트럭을 순서대로 확인합니다.
3. 현재 트럭이 다리에 올라갈 때까지 시간을 보냅니다.
4. (while 문)
   1. 시간 경과
   2. 다리가 꽉 차 있으면, 맨 앞 트럭이 다리를 건넘
   3. 현재 트럭이 다리에 올라갈 수 있는지 무게 확인
   4. 못 올라갈 경우 빈 공간을 추가하여 시간만 보냅니다.
5. 마지막 트럭이 다리를 건너는 시간을 더해줍니다.

---

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

오늘도 화이팅입니다!