문제 링크
다리를 지나는 트럭 : Level2
틀린이유
- 순서대로 들어온 순서대로 나가니까 큐로 구현해야겠다
- 다리 위에 있을 수 있는 트럭의 개수가 상이하다보니 이를 구현하는 게 포인트
- 한번에 건널 수 있을 때마다 나눠서 풀려고 함
- 그런데 여기서 완전 잘못 생각함! 😢
- 최대 10kg 이고 트럭이 [5,5,4] 일 때
- 나의 풀이로는 한 번에 2개까지만 갈 수 있지만,
- 실제로는 5가 나가고 나면 4가 바로 위에 올라올 수 있기 때문에 단계별로 시간 계산하면 오류가 생김!!!
문제 분석
문제
- 트럭 여러 대가 일차선 다리를 순서대로 건너려고 한다
- 구) 모든 트럭이 다리를 건너는데 최소 몇 초가 걸릴까?
- 트럭은 1초에 1 다리 길이만큼 움직인다
입력
- 다리 길이 == 다리에 올라갈 수 있는 트럭 수 : 1≤ bridge_length ≤ 10^4
- 다리가 버틸 수 있는 무게 : 1 ≤ weight ≤ 10^4
- 트럭의 개수 : 1≤ truck_weight ≤ 10^4
- 트럭의 무게 : 1≤ truck_weight[i] ≤ weight
구현 방법
- 순서대로 트럭이 들어가고 나가야하니까 queue
- 트럭을 움직이는 것을 어떻게 표현할 수 있을까?
- 큐에다가 가능하면 트럭 무게를 넣고, 가능하지 않으면 트럭 대신 0을 넣자! (트럭 무게 1이상이므로)
- 큐가 다리 끝에 도달하면 뒤에 트럭의 개수가 몇 개인지와 상관없이 Q.size()는 bridge_length와 일치하게 됨!
- 다리 끝에 도달하면 큐에서 제거해줌
- 마지막 트럭은 무조건 bridge_length만큼 건너간다
전체 코드
#include <bits/stdc++.h>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
queue<int> Q;
int i=0;
int w = 0;
while (true){
if (i == truck_weights.size()){
answer += bridge_length;
break;
}
answer++;
if (Q.size() == bridge_length){
w -= Q.front();
Q.pop();
}
if (w+truck_weights[i] <= weight){
Q.push(truck_weights[i]);
w += truck_weights[i];
i++;
}
else Q.push(0);
}
return answer;
}
이 글은 정말 인상적이었습니다.