https://school.programmers.co.kr/learn/courses/30/lessons/42583#qna
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
queue<int> bridge;
int cur_weight = 0;
int idx = 0;
int time = 0;
// bridge_length(다리에 최대 올라갈 수 있는 트럭 총량)만큼 무게가 0인 트럭 채우기
for (int i = 0; i < bridge_length; ++i)
{
bridge.push(0);
}
// 매 초마다 계산
while (idx < truck_weights.size())
{
time++;
// 다리의 맨 앞 트럭 제거
cur_weight -= bridge.front();
bridge.pop();
// 현재 다리의 무게 + 대기 중인 트럭 무게가 제한을 넘지 않음
if (cur_weight + truck_weights[idx] <= weight)
{
bridge.push(truck_weights[idx]);
cur_weight += truck_weights[idx];
idx++;
}
// 무게 제한을 초과한다면 빈 트럭 추가
else
{
bridge.push(0);
}
}
// 다리 위의 마지막 트럭이 통과하는 시간 계산
time += bridge_length;
return time;
}
bridge_length만큼 다리에 올라갈 수 있는 트럭의 총 개수가 제한되어있어 queue에 미리 무게가 0인 트럭을 채워 넣어놓고, 매 초마다 queue의 front를 제거하며 현재 다리 위의 트럭 무게를 갱신하도록 하면 어떨까 생각했다.
그리고 현재 다리 위의 트럭 무게가 제한 무게인 weight를 초과하면 무게가 0인 트럭을 queue에 집어 넣고 다음 시간으로 넘기고, 만약 초과하지 않는다면 queue에 다음 트럭을 채워 넣는 방식으로 문제를 해결하려 했다.
'공부 > Code Cata' 카테고리의 다른 글
소수 찾기 / 순열, DFS (0) | 2025.04.24 |
---|---|
가장 큰 수 / 정렬 (0) | 2025.04.23 |
숫자 변환(BFS) (0) | 2025.04.11 |
롤케이크 자르기 (0) | 2025.04.01 |
뒤에 있는 큰 수 찾기 / stack (0) | 2025.03.25 |