문제
BOJ 13335, 트럭
핵심
- 입력의 크기가 103이라 구현에 초점을 맞춘다.
- 다리를 n개의 트럭이 지날 때, 다리의 하중을 초과하지 않으면서 가장 빨리 다리를 건널 수 있는 시간을 구해야 하는 문제이다. 해당 트럭이 다리에 오를 수 있는지 판단하기 위해 bridge 배열을 만들었다. bridge 배열은 현재 다리에 있는 트럭의 총무게를 쉽게 구할 수 있도록 다리에 있는 트럭의 무게를 저장한다. 큐를 사용하여 현재 트럭을 다리에 올릴 수 없다면, 다리에 있는 트럭을 한 칸 앞으로 나가도록 구현하였다.
개선
- 현재 차량을 다리에 올릴 수 없다면 차량을 한 칸씩 이동시키는 대신 다리에서 가장 멀리 떨어진 차량의 거리를 구한 후 차량을 한 번에 다리 밖으로 이동시킨다면 최적화가 된다. 이미 충분히 빨라 아래 코드에선 이 부분을 구현하지 않았다. 궁금하다면, 이전에 풀었던 프로그래머스 풀이를 참고하자.
프로그래머스, 다리를 지나는 트럭 풀이
코드
시간복잡도
- O(n×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);
}
}