알고리즘 #3
less than 1 minute read
다리를 지나는 트럭
트럭이 1초마다 1씩 지나고 정해진 길이를 모든 트럭이 지나는데에 걸리는 시간을 출력하는 문제
<첫번째 시도="">
결과는 출력이 되었지만 몇몇 테스트 케이스에서 걸렸다.
시간초과가 뜨기도 했다.
```cpp
int solution(int bridge_length, int weight, vector truck_weights) {
int answer = bridge_length+1;
int now = truck_weights[0];
q.push(truck_weights[0]);
for (int j = 0; j < truck_weights.size()-1; j++) {
now += truck_weights[j + 1];
if (now <= weight) {
q.push(truck_weights[j+1]);
answer-=(bridge_length-1);
}
else{
now -= truck_weights[j+1];
}
answer+=bridge_length;
now -= q.front();
q.pop();
q.push(truck_weights[j+1]);
now+= truck_weights[j+1];
}
return answer;
}
```
<정답>
max_size를 갱신해가면서 저장할 필요가 있었다.
for문이 아닌 while문으로 동작하며 때에 맞는 조건문을 걸어주면 해결할 수 있었다.
굳이 복잡하게 배열을 사용하지 않아도 된다!!
```cpp
int solution(int bridge_length, int weight, vector truck_weights) {
int answer = 0;
int max_size = 0;
int size = 0;
for(int i=0;i<truck_weights.size();i++){
size = truck_weights[i];
while(1){
if(q.empty()){
q.push(size);
max_size+=size;
answer++;
break;
} else if (q.size() == bridge_length){
max_size-=q.front();
q.pop();
} else {
if(size+max_size > weight){
q.push(0);
answer++;
} else{
q.push(size);
max_size+= size;
answer++;
break;
}
}
}
}
return answer + bridge_length;
}
```
