[백준 13335번] 트럭 / C++

문제

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

출력

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

풀이

이전에 프로그래머스에서 이런 트럭 문제를 풀어본 적이 있다.

문제 풀러 가기 👉 프로그래머스 Level2. 다리를 지나는 트럭

이 덕분에 문제를 금방 풀긴 했는데 코드가 마음에 안 들어서 고치느라 시간이 좀 걸렸다.

그래도 마음에 안 드는 건 마찬가지다.. 언제쯤 예쁘고 보기 좋은 코드를 짤 수 있을는지..

 

먼저 기본적인 풀이 과정은 다음과 같다.

1. 다리 위에 있는 트럭을 앞으로 옮긴다.

2. 트럭을 다리에 올린다.

3. 시간 변수를 1 증가시킨다.

이 과정을 모든 트럭들이 다리를 건널 때까지 반복한다.

 

나는 해당 문제를 큐를 이용해 풀었는데 다리 위에 있는 트럭의 정보(트럭 무게, 트럭이 다리위에 있었던 시간)와 다리를 지나간 트럭의 정보(트럭 무게)를 각각 큐에 저장하도록 했다. 

* 각 큐명: truckBridge, completedTruck (변수명이 이상하더라도 살짝 흐린 눈 하고 넘어가주세욜,,^^)

먼저, 트럭을 앞으로 옮기는 로직은 다음과 같다.

1. truckBridge에서 앞에 있는 트럭의 정보를 빼낸다.

2. truckBridge를 pop 한다.

3. 해당 트럭이 다리를 빠져나갈 차례라면

   - 다리 위 트럭의 무게 합에서 해당 트럭 무게를 뺀다

   - 다리 위 트럭의 개수를 1 감소시킨다

   - completedTruck에 트럭 추가

4. 아직 다리를 빠져나갈 차례가 아니라면

   - 현재 트럭의 시간을 1 증가시킨다.

   - truckBridge에 트럭 무게와 시간을 push 한다.

이후에  트럭을 다리에 올리는 로직은 다음과 같다.

1. 현재 다리 위에 올라간 트럭의 개수와 무게 합이 주어진 조건에 맞는지 확인

2. 조건에 맞다면

   - truckBridge에 트럭 무게와 시간을 push 한다.

   - 다리 위 트럭의 무게 합에 해당 트럭 무게 더함

   - 다리 위 트럭 개수 1 증가시킴

 

글로 작성하니까 이해가 잘 안 가겠지만.. 코드를 보면 그래도 어느 정도.. 이해가 갈 것이라고.. 생각.. 합니다..(자신 없음..)

그래도 이해가 되지 않는 부분이 있다면 댓글로 남겨주세요!!

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// 다리 위에 올라간 트럭들의 무게 합, 트럭 갯수, 현재 트럭 인덱스
int sumWeight = 0, curCnt = 0, curIndex = 0;
// 입력받은 트럭의 무게를 저장하는 벡터
vector<int> inputTruck;
// 다리를 건너간 트럭을 저장하는 큐
queue<int> completedTruck;
// 다리 위에 올라간 트럭의 무게와 다리 위에 있었던 시간을 저장하는 큐
queue<pair<int, int>> truckBridge;

int main()
{
    int N, W, L, time = 0;

    cin >> N >> W >> L;
    inputTruck.resize(N);

    for (int i = 0; i < N; i++)
    {
        cin >> inputTruck[i];
    }
    // 트럭이 모두 다리를 건너기 전까지 반복문 실행
    while (completedTruck.size() != inputTruck.size())
    {
        int size = truckBridge.size();
        // 시간이 흐름에 따라 다리 위의 트럭은 앞으로 전진
        for (int i = 0; i < size; i++)
        {
            int curWeight = truckBridge.front().first;
            int curTime = truckBridge.front().second;
            truckBridge.pop();
            // 트럭이 다리를 건너면
            if (curTime == W)
            {
                sumWeight -= curWeight;
                curCnt--;
                completedTruck.push(curWeight);
            }
            else
            {
                curTime++;
                truckBridge.push({curWeight, curTime});
            }
        }
        // 트럭을 다리에 올림
        if (curIndex < N && curCnt < W && sumWeight + inputTruck[curIndex] <= L)
        {
        	truckBridge.push({inputTruck[curIndex], 1});
    		sumWeight += inputTruck[curIndex];
    		curIndex++;
    		curCnt++;
        }
        time++;
    }

    cout << time;

    return 0;
}