[백준, BOJ] 13335 - 트럭 (C++)

안녕하세요! 오늘은 BOJ 13335 - 트럭 문제를 풀어볼게요.

 

문제를 잘 읽어보면, 다음 네 가지 조건을 만족시키면서, 모든 트럭이 다리를 건너는 최단 시간을 구하라고 했네요.

• N개의 트럭이 순서를 바꾸지 않고 다리를 건넌다.
• 단위길이 w에는 트럭 w대까지 동시에 올라설 수 있다.
• 트럭은 1 단위시간에 1 단위길이만큼만 이동할 수 있다.
• (동시에 다리 위에 올라서있는 트럭들의 무게의 합) <= 다리의 최대하중 L

문제에서 제시해준 예시를 같이 살펴보면서, 어떻게 구현해야 할지 생각해 볼게요.

접근

 

다리의 길이 w = 2이고, 최대하중 L = 10, 트럭은 {7, 4, 5, 6} 순서로 대기 중인 상황이에요.

 

Step_1)

1. 우선 다리 위에는 트럭이 없어요.

2. 다리에 진입하지 못한 가장 앞 트럭을 다리로 이동시켜요. (순서를 바꾸지 않음)

 

Step_2)

1. 이제 다리 위에 트럭이 있으니, 다리 위 트럭은 앞으로 한 칸 이동해야 하고, 다리를 모두 건넜는지 확인해 줘요.아직 다리를 건너지는 못했네요.

2. 그리고 다리에 진입하지 못한 가장 앞 트럭을 다리로 이동시킬 것인데, 이때 최대 하중을 생각해봐야 해요.

이미 다리에는 7의 하중이 이미 가해져 있으니, 4의 트럭이 추가될 경우 최대하중 L = 10보다 커지니 다리에 트럭이 들어오면 안 돼요.

이 상황은 아니지만 문제 조건에 따라 이미 w대가 다리에 있는 경우에도 다리에 트럭이 들어와서는 안돼요.

 

Step_3)

1. 다리 위에 트럭이 있으니, 다리 위 트럭은 앞으로 한 칸 이동해야 하고, 다리를 모두 건넜는지 확인해 줘요.

무게가 7인 앞쪽 트럭이 다리를 모두 건넜으니, 다리를 건넌 트럭 한 대를 카운팅 해주어요. 이 과정을 모든 트럭이 건널 때까지 반복해야 하겠네요.

2. 그리고 다리에 진입하지 못한 가장 앞 트럭을 다리로 이동시켜요.

다리 위에 트럭이 없으니 당연히 트럭이 최대 하중보다 작거나 같을 것이고, 진입시켜도 괜찮아요.

 

 

Step_4)

1. 다리 위에 트럭이 있으니, 다리 위 트럭은 앞으로 한 칸 이동해야 하고, 다리를 모두 건넜는지 확인해 줘요.

다리를 아직 다 건너지 못했으니 다음 단계로 넘어가요.

2. 다리에 진입하지 못한 가장 앞 트럭을 다리로 이동시켜요.

이때 최대 하중을 생각해봐야 하는데, 4+5 <= 10이므로 트럭을 다리로 이동시켜도 괜찮아요.

 

Step_5)

1. 다리 위에 트럭이 있으니, 다리 위 트럭은 앞으로 한 칸 이동해야 하고, 다리를 모두 건넜는지 확인해 줘요.

무게가 4인 앞쪽 트럭이 다리를 모두 건넜으니, 다리를 건넌 트럭 한 대를 카운팅 해주어요.

이제 두 대가 다리를 건넜고, 아직 네 대가 모두 다리를 건너지 않았으니 반복을 계속해요.

2. 다리에 진입하지 못한 가장 앞 트럭을 다리로 이동시켜요.

이때 최대 하중을 생각해봐야 하는데, 5+6 > 10이므로 트럭을 다리로 이동시키면 안돼요.

 

 

Step_6)

1. 다리 위에 트럭이 있으니, 다리 위 트럭은 앞으로 한 칸 이동해야 하고, 다리를 모두 건넜는지 확인해 줘요.

무게가 5인 앞쪽 트럭이 다리를 모두 건넜으니, 다리를 건넌 트럭 한 대를 카운팅 해주어요.

이제 세 대가 다리를 건넜고, 아직 네 대가 모두 다리를 건너지 않았으니 반복을 계속해요.

2. 다리에 진입하지 못한 가장 앞 트럭을 다리로 이동시켜요.

이때 최대 하중을 생각해봐야 하는데, 이미 다리에 트럭이 없기도 하고, 6 <= 10이므로 트럭을 다리로 이동시켜도 괜찮아요.

 

Step_7, 8) 이제 무게가 6인 트럭이 한 칸씩 앞으로 이동해서 다리를 모두 건너게 되고, 네 대가 모두 건넜으니 반복을 종료해야 하겠네요.

 

차근차근 살펴봤는데, 매 step마다 (= 1 단위시간이 지날 때마다)

1. 다리 위에 트럭이 있다면, 모든 트럭을 앞으로 한 칸씩 전진시킨다. 2. 맨 앞 트럭이 다리를 모두 건넜다면, 다리에서 벗어났으므로 하중에서 제외시키고 다리를 건넌 트럭 한 대를 카운팅해준다. 3. 다리에 진입하지 못한 트럭이 있다면, (현재 다리 위 하중 + 새로 들어올 트럭의 하중) <= (최대 하중)이고, 다리 위 트럭이 w개  미만일 경우 트럭을 다리에 진입시킨다. 4. 트럭이 모두 다리를 건널 때까지 반복한다.

 

의 과정이 진행되니, 이대로 구현해 주면 되겠네요.

 

구현

 

#include <iostream>
#include <queue>
#include <deque>
#define X first
#define Y second
using namespace std;

queue<pair<int, int>> Q;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, w, L;
    cin >> n >> w >> L;

    for (int i = 0; i < n; i++) {
        int truck;
        cin >> truck;
        Q.push({truck, w}); // 큐에 트럭 무게와 다리 길이 저장
    } 

    int weight = 0; // 다리 위 현재 하중(트럭 무게 합) 저장
    int time = 0; // 단위 시간 저장
    int cnt = 0; // 다리를 건넌 트럭 대수 저장
    
    deque<pair<int, int>> bridge; // 다리 위로 진입한 트럭을 관리할 deque
    while (cnt != n) { // 다리를 n대의 트럭이 모두 건널 때까지 반복
        time++; // 시간 증가

        for (int i = 0; i < bridge.size(); i++) { // 다리 위 모든 트럭에 대해서 1칸씩 전진 (= 남은 거리 1 감소)
            bridge[i].Y--;
        }

        if (!bridge.empty() && bridge.front().Y == 0) { // 맨 앞 트럭이 다리를 모두 건넜을 경우 (= 남은 거리 0)
            weight -= (bridge.front().X); // 다리에서 벗어났으므로 하중에서 제외
            bridge.pop_front(); // 다리 deque에서 제외
            cnt++; // 다리를 건넌 트럭 대수 카운팅
        }

        if (!Q.empty()) { // 만약 다리에 진입하지 않은 트럭이 있다면
            pair<int, int> cur = Q.front();
            if (weight + cur.X > L || bridge.size() >= w) continue;
            // 만약 현재 다리 위 트럭 무게에 새로운 트럭이 들어가면 최대하중을 넘길 경우 skip
            // 또는 다리 위 트럭이 이미 w개 이상일 경우 skip
            else {
                weight += cur.X; // 다리 위 트럭 무게 증가
                bridge.push_back(cur); // 다리 위에 올라서기
                Q.pop(); // 대기 중인 트럭 큐에서 제외
            }
        } 
    }

    cout << time; // 최단시간 출력
    return 0;
}

 

처음에 입력받은 트럭 무게를 {트럭 무게, 다리 길이} 형태의 pair로 큐에 저장해 줘요.

 

큐는 마치 줄을 서는 것처럼, FIFO(First In First Out), 즉, 처음 입력된 자료가 맨 처음 출력되는 자료구조예요. 트럭이 순서를 바꾸지 않고 다리에 올라서니, 대기 중인 트럭들을 큐에 저장해 주었어요.

덱은 앞과 뒤 모두 데이터의 삽입과 삭제가 가능한 자료구조예요. 덱으로는 다리 위의 트럭들을 관리할 거예요.

 

while 문 안을 살펴볼게요.

단위 시간 time을 증가시켜 주고, 다리 위 모든 트럭에 대해 1칸씩 전진해 줘요.

결국 다리의 끝까지 전진한다는 것은 "다리의 길이 만큼이 트럭의 이동 거리"이고, 남은 이동 거리가 1씩 감소한다는 것을 의미하므로, bridge [i]. Y--; 로 구현했어요.

맨 앞 트럭이 다리를 모두 건넜을 경우는 남은 이동 거리가 0이 됐을 때와 동치이므로, 그 경우 다리 덱에서 제외해 주고, 다리에 걸리는 하중에서 트럭의 무게를 빼줘야 해요.

또, cnt를 1 증가시켜 주어서 다리를 건넌 트럭 대수를 카운팅 해줘요.

다리에 진입하지 않은 트럭이 있어서 큐가 비지 않았다면, 대기 중인 가장 앞 트럭의 무게를 현재 다리에 걸리는 하중에 더해줬을 때 최대 하중 L을 넘길 경우, 또는 이미 다리에 진입한 트럭의 수가 w 이상일 경우에는 continue로 다리에 진입시키지 않아요.

그 외의 경우 다리에 진입할 수 있으므로 다리에 걸리는 하중에 트럭의 무게를 증가시켜 주고, bridge 덱에 트럭을 push 해주었어요.

그리고 대기 차량 큐에서는 pop으로 제외시켜 줘요.

 

n대의 트럭이 모두 다리를 건너서 반복문을 마치면 최소시간 time을 출력해 주면 돼요.