문제
접근
문제 예시에서 보여준 것처럼 생각했다.
다리 위에 있는 트럭들을 나타내는 큐를 하나 만들어서 1초 단위로 움직여주며 생각했다.
매초마다 다리위에 트럭들은 한칸씩 전진하고, 무게에 여유가 있다면 새로운 트럭이 올라오고, 안된다면 빈 공간을 올리는 식으로 하였다.
예를 들어, 다리 길이가 5이고, 최대 허용무게가 10이면
[0, 0, 0, 0, 0]
인 큐를 만들고, 트럭을 하나씩 append 해준다.
진행방향은 오른쪽에서 왼쪽이다.
[0, 0, 0, 0, 7]
[0, 0, 0, 7, 3]
[0, 0, 7, 3, 0]
이런식으로 진행하면서 다리위의 트럭들의 무게가 0이면 모든 트럭이 지나간 것이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(bridge_length, weight, truck_weights):
onQ = [0] * bridge_length
answer = 0
now_weights = 0
while True:
answer += 1
now_weights -= onQ.pop(0)
if len(truck_weights) and weight >= truck_weights[0] + now_weights:
truck_weight = truck_weights.pop(0)
onQ.append(truck_weight)
now_weights += truck_weight
else:
onQ.append(0)
if now_weights == 0:
break
return answer
- C++ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <queue>
#include <vector>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
queue<int> on_q;
int answer = 0;
int now_weight = 0;
int i = 0;
for(int i = 0; i<bridge_length;i++){
on_q.push(0);
}
while(1){
answer++;
now_weight -= on_q.front();
on_q.pop();
if (truck_weights.size() > i && weight >= now_weight + truck_weights[i]){
now_weight += truck_weights[i];
on_q.push(truck_weights[i]);
i++;
}
else{
on_q.push(0);
}
if(now_weight == 0){
break;
}
}
return answer;
}