트럭( BOJ 13335 )

문제 : https://www.acmicpc.net/problem/13335

13335번: 트럭

 

문제 파악하기

N개의 트럭이 다리를 건너는데 필요한 최소 시간을 구하는 문제입니다. 트럭의 순서는 바꿀 수 없으며, 모든 트럭은 다리를 건너는데 W만큼의 시간이 걸립니다. 최대 하중인 L을 넘지 않는 선에서 모든 트럭이 다리를 건너는데 필요한 최소 시간을 구하기 위해서는 현재 다리를 건너고 있는 트럭의 총 하중을 고려하여 직접 시뮬레이션 할 수 있습니다. 또는 트럭이 다리를 모두 건너는데 필요한 시간에 초점을 맞춰서 구할 수도 있습니다.

 

문제 해결하기

가장 간단한 방법은 시간을 하나씩 증가시키면서 시뮬레이션 하는 알고리즘이 있습니다. 이 알고리즘은 트럭의 개수가 많아지거나 시간이 오래 걸릴수록 효율이 떨어지게 됩니다. 하지만 이 문제에서는 트럭의 개수도 작으며, 다리의 길이도 작기에 충분히 모든 과정을 시뮬레이션할 수 있습니다.

또다른 방법은 모든 과정을 시뮬레이션 하지 않고 특정 과정만 시뮬레이션 하는 방법이 있습니다. 사실 생각해보면 트럭이 다리 위에서 움직이는 과정은 시뮬레이션할 필요가 없습니다. 트럭이 움직이는 과정 중 중요한 순간은 다리에 올라가는 순간과 내려가는 순간입니다. 따라서, 우리는 트럭이 언제 다리에 올라가서 내려가는지를 시간 변수(curT)에 기록하면 충분히 문제를 해결할 수 있습니다.

그럼 언제 트럭이 다리에 올라가는지 알 수 있을까요? 트럭이 다리에 올라가는 경우의 수는 총 2가지입니다. 첫 번째, 다리의 하중이 여유로운 경우입니다. 이 경우에는 그냥 다리에 올라가면 되며, 시간 변수의 값(curT)을 1 증가시켜 주면 됩니다. 두 번째, 다리의 하중이 여유롭지 못한 경우입니다. 이 경우에는 이미 올라간 트럭들을 빼주어야 하며, 이 때에 나가는 트럭의 시간들을 확인할 필요가 있습니다. 내려가는 트럭들이 현재 시간보다 먼저 내려갈 수도 있기 때문에 내려가는 트럭들의 시간(tmpT)와 현재 시간(curT+1) 중 더 큰 값을 저장해주어야 합니다.

이렇게 올라가는 현재 시간을 구했다면 내려가는 시간은 금방 구할 수 있습니다. 현재 시간(curT)에서 다리의 길이(W)만큼 더해주면 됩니다. 이렇게 올라가는 시간과 내려가는 시간을 구하고, 트럭들을 큐를 활용하여 처리하면 어렵지 않게 해결할 수 있습니다.

 

소스코드

#import <stdio.h>
#import <queue>
#import <vector>
#import <utility>
#define PAIR pair<int, int>
using namespace std;
 
int N, W, L, t, w;
vector< int > inp;
 
int curW, tmpT, curT;
queue< PAIR > q;
 
int main() {
    // input
    scanf("%d %d %d", &N, &W, &L);
    for(int i=0;i<N;i++) {
        scanf("%d", &t);
        
        inp.push_back(t);
    }
    
    // sv
    curT = -1;
    for(int i=0;i<N;i++) {
        
        // 트럭 바로 건너기
        if(curW+inp[i] <= L) curT++;
        else {
            // 다리에서 트럭 빼기
            while(!q.empty() and curW+inp[i]>L) {
                w = q.front().first;
                tmpT = q.front().second;
                q.pop();
                
                curW -= w;
            }
            
            curT = max( curT+1, tmpT );
        }
        
        q.push({inp[i], curT+W});
        curW += inp[i];
        
    }
    
    // 마지막 트럭의 끝나는 시간
    printf("%d", curT+W+1);
}
 

후기

직접 시뮬레이션 돌리지 않으니 알고리즘을 떠올리기 귀찮은 문제였습니다. 예외 케이스도 종종 생겨서 생각보다 오래 걸린 문제로, 다리의 길이가 좀 더 길어지면 문제가 더 재미있지 않을까 생각이 듭니다.