문제

BOJ 13335, 트럭

핵심

• 입력의 크기가 $10^3$이라 구현에 초점을 맞춘다.
• 다리를 n개의 트럭이 지날 때, 다리의 하중을 초과하지 않으면서 가장 빨리 다리를 건널 수 있는 시간을 구해야 하는 문제이다. 해당 트럭이 다리에 오를 수 있는지 판단하기 위해 bridge 배열을 만들었다. bridge 배열은 현재 다리에 있는 트럭의 총무게를 쉽게 구할 수 있도록 다리에 있는 트럭의 무게를 저장한다. 큐를 사용하여 현재 트럭을 다리에 올릴 수 없다면, 다리에 있는 트럭을 한 칸 앞으로 나가도록 구현하였다.

개선

• 현재 차량을 다리에 올릴 수 없다면 차량을 한 칸씩 이동시키는 대신 다리에서 가장 멀리 떨어진 차량의 거리를 구한 후 차량을 한 번에 다리 밖으로 이동시킨다면 최적화가 된다. 이미 충분히 빨라 아래 코드에선 이 부분을 구현하지 않았다. 궁금하다면, 이전에 풀었던 프로그래머스 풀이를 참고하자.
  프로그래머스, 다리를 지나는 트럭 풀이

코드

시간복잡도

• $O(n \times w)$

C++

#include <iostream>
#include <queue>
using namespace std;

int n, w, l;
int trucks[1004];
int bridge[1004];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> w >> l;
	queue<int> q;
	for (int i = 0; i < n; ++i) {
		int weight;
		cin >> weight;
		q.push(weight);
	}
	int time = 0;
	while (!q.empty()) {
		auto cur = q.front(); 
		for (int i = w; i >= 1; --i) 
			bridge[i] = bridge[i - 1];
		bridge[0] = 0;
		int curWeight = 0;
		for (int i = 0; i < w; ++i)
			curWeight += bridge[i];
		++time;
		if (curWeight + cur <= l) {
			bridge[0] = cur;
			curWeight -= cur;
			q.pop();
		} 
	}
	cout << time + w << '\n';
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] bridge = new int[1004];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            int weight = Integer.parseInt(st.nextToken());
            q.add(weight);
        }
        int time = 0;
        while (!q.isEmpty()) {
            for (int i = w; i >= 1; --i)
                bridge[i] = bridge[i - 1];
            bridge[0] = 0;
            int curWeight = 0;
            for (int i = 0; i < w; i++)
                curWeight += bridge[i];
            ++time;
            if (curWeight + q.peek() <= l) {
                bridge[0] = q.peek();
                curWeight -= q.poll();
            }
        }
        System.out.println(time + w);
    }
}