[백준(BOJ)] 13335번 트럭 C++

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

13335번: 트럭

 

 

어떤 문제인가?

문제가 길다.

간단히 말하면 n대의 트럭이 길이가 w인 다리를 건널 때 다리의 최대하중인 L을 지켜가며 건너야 한다.

이때 모든 트럭이 다리를 건너는 최소 시간을 출력하면 된다.

 

 

접근 방법

 

queue<int> truck;
deque<pair<int, int>> bridge;

아직 다리에 올라가지 않은 트럭들은 queue를 사용해 저장한다.

다리에 올라간 트럭은 deque와 pair를 통해 first에는 트럭의 무게를 second에는 트럭이 다리의 어느 지점에 있는지를 저장한다.

 

 

int n, w, l;
cin >> n >> w >> l;

for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    truck.push(a);
}

문제의 조건에 맞게 변수들을 입력받는다.

또, queue에 트럭의 무게들을 입력받아 저장한다.

 

 

int cnt = 0;
int total = 0;

걸린 시간을 측정할 cnt와 다리 위에 있는 트럭들의 무게를 저장할 total을 모두 0으로 초기화한다.

 

while (true) {
    if (truck.empty() && bridge.empty()) {
        cout << cnt + 1;
        break;
    } else {
        cnt++;
    }

    if (!truck.empty() && total + truck.front() <= l) {
        bridge.push_back(pair<int, int>(truck.front(), 0));
        total += truck.front();
        truck.pop();
    }

    for (int i = 0; i < bridge.size(); i++) {
        bridge[i].second++;
    }

    if (bridge.front().second == w) {
        total -= bridge.front().first;
        bridge.pop_front();
    }
}

이제 while문을 반복하며 기능을 수행할 것이다.

먼저 queue와 deque가 모두 비었다는 소리는 모든 트럭들이 지나갔다는 말이다.

그렇기 때문에 cnt + 1을 출력하고 break를 통해 탈출한다.

+1을 해주는 이유는 마지막 트럭이 다리의 마지막 지점에 있다가 다리를 통과할 때를 세어주는 것이다.

queue와 deque가 모두 비어있지 않다면 cnt를 1 증가시켜준다.

 

 

이제부터 무게에 대한 연산을 할 것이다.

queue가 비어있지 않고, 현재 다리 위에 있는 트럭의 무게(total) + queue의 front(새로 다리에 올라갈 트럭의 무게)가 다리의 최대하중보다 작거나 같다면, 

deque에 트럭의 무게와 트럭의 위치 0을 추가해준다.

total에 새로 추가된 트럭의 무게를 더해준다.

queue를 pop 해준다.

 

그리고 이제 한 칸씩 앞으로 움직인다.

-> deque 원소의 모든 secnod를 1 증가시켜주면 된다.

 

만약 deque의 front의 second가 다리의 길이(=w)라면  다리를 통과했다는 말이다.

따라서 total에서 통과한 트럭의 무게를 빼주고, deque를 pop_front 해주면 된다.

 

 

 

무엇이 어려웠는가?

역시나 문제를 풀기 전에 자료구조를 선택해야 했다.

아직 다리에 올라가지 않은 트럭들은 queue를 사용하기로 문제를 읽고 바로 떠올릴 수 있었다.

하지만 다리 위에 있는 트럭들을 어떻게 처리해야 할지 고민을 많이 했다.

다리의 길이와 최대하중을 고려해야 해서 어려웠던 것 같다.

자료구조를 선택하는 것이 항상 어려운 난관이다.

자료구조를 선택하면 그 뒤부터는 수월하다. 

 

문제를 풀고 코드를 보니 정말 문제를 고대로 코드로 옮겨 놓은 것 같은데 왜 어렵다고 느껴졌는지....

 

배운 점

항상 말하고 항상 느낀다... 문제를 읽고 빠르게 자료구조를 선택할 수 있는 능력이 정말 중요하다.

너무 많이 말했지만 항상 느끼고 배우는 것이라 어쩔 수 없다..

 

 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/13335.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.