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

🔐 프로그래머스 - 다리를 지나는 트럭

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

🔑 풀이

이 문제를 풀기 위한 주요 아이디어는 현재 다리를 건너는 트럭의 무게와 위치를 관리하며 트럭이 일정

시간 동안 다리를 이동하는 과정을 시뮬레이션하는 것이다. 트럭이 다리에 올라가거나 내려갈 때마다 현재

무게를 조정하면서, 모든 트럭이 다리를 건너는 최소 시간을 구한다.

다리가 버틸 수 있는 무게 제한과 다리를 동시에 건널 수 있는 트럭의 수(bridge_length)가 주어지며,

각 트럭이 순서대로 다리를 건널 때, 모든 트럭이 건너는 데 걸리는 최소 시간을 계산하는 문제이다.

다리를 건너는 트럭을 시간에 따라 관리하기 위해 큐(queue)를 사용한다. 큐는 pair<int, int> 형식으로

구성되며, 각 트럭의 (도착 시간, 무게)를 저장한다. 이렇게 하면 다리에 트럭이 올라가는 순서대로 큐에서

관리할 수 있다. 문제 풀이를 위한 알고리즘은 다음과 같다.

1. 트럭이 다리를 모두 건널 때까지 반복한다. 다리에 있는 트럭의 무게와 현재 시간에 따라 큐를
   업데이트하고, 다음 트럭이 다리에 오를지 여부를 결정한다.

2. 큐에서 트럭 제거: 현재 시간이 q.front().first와 같거나 크면, 해당 트럭이 다리를 완전히
                 건넜음을 의미한다. 트럭을 큐에서 제거하고, cur_weight에서 트럭의 무게를 뺀다.

3. 다음 트럭 추가: 현재 트럭이 다리에 추가될 수 있는지 확인한다. 다리 위에 있는 총 무게가
                weight 제한을 넘지 않는다면, 트럭을 큐에 추가한다.

4. 시간 증가: 매 반복마다 시간을 1 증가시킨다.

🧩 코드