[스택/큐] 다리를 지나는 트럭
|| 문제설명 ||
- 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 한다.
- 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 한다.
- 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딘다.
(※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.)
이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성해라.
- bridge_length : 다리 길이
- weight : 다리가 견딜 수 있는 무게
- truck_weights : 트럭별 무게
_ bridge_length : 1 이상 10,000 이하
_ weight : 1 이상 10,000 이하
_ truck_weights의 길이 : 1 이상 10,000 이하
_ 모든 트럭의 무게 : 1 이상 weight 이하
|| 문제해결방법 ||
|| 코드 ||
[2020.09.30] 성공
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0, w= 0, in = 0, out = 0;
queue<int> q;
while(out < truck_weights.size()) {
if(in < truck_weights.size()) {
if(w + truck_weights[in] <= weight) {
q.push(truck_weights[in]);
w += truck_weights[in];
in++;
}
else q.push(0);
}
else q.push(0);
if(q.size() == bridge_length) {
w -= q.front();
if(q.front() > 0) out++;
q.pop();
}
answer++;
}
return answer + 1;
}
[2021.01.16]
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0, total_weight=0, top = 0;
queue<int> bridge;
while(1) {
if(bridge.size() == bridge_length) {
if(bridge.front() == -1) break;
total_weight -= bridge.front();
bridge.pop();
}
if(top < truck_weights.size()) {
if(total_weight + truck_weights[top] <= weight) {
total_weight += truck_weights[top];
bridge.push(truck_weights[top++]);
}
else bridge.push(0);
}
else bridge.push(-1);
answer++;
}
return answer;
}
Author And Source
이 문제에 관하여([스택/큐] 다리를 지나는 트럭), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yerin6860/스택큐-다리를-지나는-트럭저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)