[고득점 KIT] 다리를 지나는 트럭 cpp

문제
트럭 여러 대가 다리를 지나려고 한다.
다리는 길이와 한 번에 견딜 수 있는 무게를 갖고있다.
트럭은 1초에 1만큼 이동을 하고 다리가 견딜 수 있는 무게를 초과해서 트럭이 들어올 수 없다.
다리의 길이, 무게와 트럭들의 무게가 입력으로 들어올 때 모든 트럭이 순서대로 다리를 건너는 최소시간을 출력하라.

입력
다리길이, 다리무게, 트럭들의 무게가 입력된다.

출력
트럭이 다리를 모두 건너는 최소시간을 출력한다.

---

접근

트럭을 이동할 때마다 현재 다리 위에있는 트럭들의 무게와 트럭을 다리 길이만큼 이동시켜야 했다. 현재 무게를 측정하는 것은 어렵지 않았지만 트럭의 이동을 어떻게 모델링할지 많은 고민을 하였다.

그러던 중 다리를 큐로 모델링하여 트럭이 이동하는 것이 아니라 트럭이 들어오면 큐가 움직이는 생각을 하였다. 그래서 다리가 견딜 수 있는 무게라면 트럭을 큐에 넣고 그렇지 않다면 0을 넣었다. 

큐는 다리 길이만큼의 칸이 있다고 생각하고 0은 빈 칸을 의미하도록 한다.

 

구현

다리의 길이만큼 큐에 0을 넣어 빈 칸을 만들어준다.

    for(int i=0;i<bridge_length-1; i++){
        q.push(0);
    }

 

idx는 다음 큐에 넣을 트럭을 카리키며 cur_weight는 현재 다리 위에있는 트럭들의 무게를 나타낸다.

    int idx=0;
    int cur_weight = 0;

 

while문으로 반복을 하며 idx가 마지막 트럭 다음을 가리키면 종료된다.

먼저 cur_weight와 다음 트럭의 무게를 더하여 다리가 견딜 수 있다면 큐에 추가를 하고 다음 트럭을 가리키도록 한다.

만약 다리가 견딜 수 없다면 큐에 0을 추가한다.

위 두 과정 이후에는 맨 앞에 있는 것을 빼준다. 여기서 빈 칸은 0이기 때문에 현재 무게에 빼줘도 영향을 받지 않는다.

    while(idx<trucks.size()){
        answer++;
        // 현재 무게+그 다음 트럭 무게가 다리 무게이하라면
        if (cur_weight+trucks[idx]<=weight)
        {
            cur_weight += trucks[idx];
            q.push(trucks[idx]);
            idx++;
        }
        else{
            q.push(0);
        }

        cur_weight -= q.front();
        q.pop();

    }

 

while문이 종료되면 최종해에 다리 길이만큼 더해서 출력하는데, 마지막 트럭은 가리키기만하고 이동시키지 않았기 때문에 마지막트럭이 이동하는 시간을 더한 것이다.

    answer += bridge_length;
    return answer;

---

전체 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int bridge_length, int weight, vector<int> trucks) {
    int answer = 0;
    queue<int> q;


    // 초기에 다리 길이만큼 큐에 0을 넣음
    for(int i=0;i<bridge_length-1; i++){
        q.push(0);
    }

    int idx=0;
    int cur_weight = 0;
    // 현재 idx가 마지막 트럭을 가리키면 종료
    // idx가 마지막 트럭 가리킬 때 answer에 +다리길이해줌
    while(idx<trucks.size()){
        answer++;
        // 현재 무게+그 다음 트럭 무게가 다리 무게이하라면
        if (cur_weight+trucks[idx]<=weight)
        {
            cur_weight += trucks[idx];
            q.push(trucks[idx]);
            idx++;
        }
        else{
            q.push(0);
        }

        cur_weight -= q.front();
        q.pop();

    }
    answer += bridge_length;
    return answer;
}

---

느낀점

먼저 문제를 읽고 시뮬레이션을 해보는 것이 좋다. 그러면 문제에 대해 접근할 수 있는 방법이 떠오르기도 하고, 문제에 주어진 것을 벗어나 새로운 관점에서 바라볼 필요가 있었다. 예를 들면 트럭이 움직이는 것 대신 다리가 움직이도록 하는 것이다. 실제에는 다리가 움직이지 않지만 코드로 모델링을 할 때는 다리가 움직이도록 표현해도 되기 때문이다.

 

그리고 문제에서 주어진 것들을 표현할 때 어떤 자료구조를 사용해야 유리할지 고민 해보는 것도 좋다.