백준 13335 트럭 C++ [컴공과고씨]

https://www.acmicpc.net/problem/13335

13335번: 트럭

이 문제 같은 경우는 2개의 케이스로 나누어서 풀어주었다.

첫 번째는 트럭이 올라갈 때 다리의 무게가 버틸 수 있어 트럭이 올라갈 수 있는 경우와 트럭이 다리를 다 건넌 경우로 나누어 주었다. 

트럭이 출발하면 큐에 넣을 건데 이 때 그 트럭의 무게와 언제 다리를 다 건너는지 도착 시간을 pair를 이용해서 넣어주는 것이 핵심이다.

큐를 쓰는 이유는 먼저 들어간 트럭이 먼저 다리를 통과하기 때문에 큐를 쓰는 것이다.

 

단계별 풀이

1. 먼저 트럭을 받을 큐(q)와 다리위의 올라간 트럭을 관리할 큐(q2) 선언

2. while문이 한번 반복할 때 마다 1초씩 증가

3. 만약 다리 위의 트럭이 도착 시간이 지났다면 다리 위의 무게에서 현재 트럭 무게를 빼주고 q2.pop

4. 만약 다음 트럭이 올라 갈 수 있는 무게가 된다면 도착시간(현재시간 + 다리의 길이 -1) 을 q2에 push

 

 

전체코드

#include <iostream>
#include <queue>
using namespace std;
int main(){
    int t, n, w, l, weight = 0;
    queue<int> q;
    queue<pair<int, int>> q2;
    bool can = true;
    int ans = 0;
    cin >> n >> w >> l;
    for (int i = 0; i < n;i++){
        cin >> t;
        q.push(t);
    }
    int time = 0;
    bool start = true;
    while(!q2.empty() || start){
        start = false;
        time++;
        if(!q2.empty() && time > q2.front().second){ 
            // 트럭 다리를 통과
            weight -= q2.front().first;
            q2.pop();                        
        }
        if(!q.empty() && weight+q.front() <= l){ // 다리위 트럭 추가
            q2.push(make_pair(q.front(), time + w - 1));
            weight += q.front();
            q.pop();
        }        
    }
    cout << time;
    return 0;
}

체감 난이도	걸린시간	참고	사용 문법
중하	31min	x	큐 (queue)