[BOJ] 13335번 | 트럭 (C++)

🔗문제 보러가기

13335번: 트럭

 

🧑🏻‍💻풀이 과정

1. 다리를 건너기 위해 대기 중인 트럭들, 다리를 건너는 중인 트럭들을 관리할 2개의 큐(Queue)를 선언합니다.
2. 해당 2개의 큐가 모두 비었다면, 반복문을 종료합니다.
3. 아니라면, 다리를 건너는 트럭들 중 맨 앞 트럭이 다리를 건넜는지 확인합니다.
   • "경과시간 - 해당 트럭이 다리에 진입한 시각 = 다리의 길이"라면, 다리를 건넜습니다.
     • 이 경우, 총 무게에서 해당 트럭 무게를 빼주고, 다리를 건너는 트럭들 큐에서 pop 해줍니다.
4. "총 무게 + 다리를 건널 다음 트럭의 무게"가 다리의 최대 하중 이하인지 확인합니다.
   • 최대 하중 이하라면, 해당 트럭을 다리를 건너는 트럭들 큐에 넣어주고, 대기 트럭 큐에서 pop 합니다.
   • 총 무게에 해당 트럭의 무게를 더해줍니다.
5. 경과시간을 +1 합니다.
6. 2번 조건을 만족할 때까지, 3~5번 과정을 반복합니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <queue>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;

struct Truck
{
    Truck() { }
    Truck(int weight, int enterTime) : _weight(weight), _enterTime(enterTime){ }
    int _weight;
    int _enterTime;
};

void CheckTheTruckOnBridge(queue<Truck>& trucks, const int totalTime, const int bridgeLength, int& currentWeight)
{
    // 다리 위의 트럭들 중 맨 앞 트럭이 다리를 다 지났는지 체크
    while (!trucks.empty())
    {
        Truck frontTruck = trucks.front();

        // 다리를 다 건넌 경우, 총 무게에서 해당 트럭 무게 빼기
        if (totalTime - frontTruck._enterTime == bridgeLength)
        {
            currentWeight -= frontTruck._weight;
            trucks.pop();
        }

        break;
    }
}

int main()
{
    FAST_IO

    int truckNums, bridgeLength, bridgeMaxWeight;
    cin >> truckNums >> bridgeLength >> bridgeMaxWeight;

    queue<int> trucks;
    for (int i = 0; i < truckNums; i++)
    {
        int weight;
        cin >> weight;
        trucks.emplace(weight);
    }

    queue<Truck> trucksOnBridge;
    int currentWeight = 0, totalTime = 0;

    while (true)
    {
        if (trucks.empty() and trucksOnBridge.empty())
            break;

        CheckTheTruckOnBridge(trucksOnBridge, totalTime, bridgeLength, currentWeight);

        // 다리 위에 트럭을 올릴 수 있을 경우 올리기
        if (!trucks.empty() and currentWeight + trucks.front() <= bridgeMaxWeight)
        {
            int currentTruckWeight = trucks.front();
            trucksOnBridge.push(Truck(currentTruckWeight, totalTime));

            currentWeight += currentTruckWeight;
            trucks.pop();
        }

        totalTime++;
    }

    cout << totalTime;
    return 0;
}