13335 - 트럭 (큐, 시뮬레이션)

13335 - 트럭

난이도: 실버1

구현방법: 시뮬레이션, 구현

문제 

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

1 초

512 MB

9666

5039

4021

54.478%

문제

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

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

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

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

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>

using namespace std;
vector <int> truck(1001);
int n, w, L, ans;
int isOnBridge[1001] = {0, };
/*
풀이 방법: 다리의 부하가 넘지 않는 선에서 최대한으로 트럭을 다리위로 건너게 만든다.
차가 2대 이상 함께 지나갈 때는 첫 차가 통과하는데 걸리는 시간 w + 연달아 들어오는 차들이 도착하는 데 걸리는 시간(차의 수) 를 해준다.

ver 2.0 : 다리 부하가 걸리지 않는 수준이되면서 다음차가 다리를 건너기 시작할 수 있으면 건너기 시작하게끔 구현한다. 시간은 1씩 증가시키면서!
ver 3.0 : 배열에 차례대로 트럭의 이동을 그대로 구현한다.  : 단위시간이 지나면 버스가 한칸 이동. 

4 2 10
7 4 5 6

*/

void crossBridge()
{
    
    int t = 0;
    int curweight = 0;
    int idx = 0;//버스 번호
    for(int i = 0; i < w; i++) //트럭 위치 초기화 : -1은 그 위치에 트럭 없음
        isOnBridge[i] = -1;
    while(1)
    {
  
        if(isOnBridge[w-1] != -1) //한 트럭이 다리를 끝까지 도달한 경우, 현재 다리 부하를 뺀다.
        {
            curweight -= truck[isOnBridge[w-1]];
            isOnBridge[w-1] = -1;
        }
        for(int i = w-1; i > 0; i--)//트럭 하나씩 이동, (실행 후 bridge[0]은 항상 비어있다.)
        {
            if (isOnBridge[i-1] != -1)
            {
                // cout << " i : " << i << endl;
                isOnBridge[i] = isOnBridge[i - 1];
                isOnBridge[i - 1] = -1;
            }
        }
        t++;
        if(curweight + truck[idx] <= L)
        {
            // cout << "idx : " << idx << endl;
            isOnBridge[0] = idx;
            curweight += truck[idx];
            idx++;
        }
        if(curweight == 0)
            break;


    }
    cout << t;
}

int main()
{
    cin >> n >> w >> L;
    for(int i = 0; i < n; i++)
    {
        cin >> truck[i];

    }
    crossBridge();
}

 

Comment

• 시뮬레이션, 구현 문제 같은 문제입니다.
• 트럭이 다리위를 건너가는 것을 isOnBridge 위에서 idx값을 옆 칸으로 이동하면서 넣어주는 걸로 구현했습니다. (crossBridge 함수 내 while 문 안에 for문)
• 트럭이 다리 끝에 도달했다면 현재 무게 curweight에서 트럭무게를 빼주고, 다시 그 위치에 -1로 아무것도 없다는 표시를 해주었습니다.
• 요즘 코테에서 이런 비슷한 문제 접해봤던 것 같은데 단위시간은 계속 흐르고, 차의 이동을 배열내에서 값을 이동시키는 걸로 구현하는 게 인상 깊었습니다.
• 구현이 어려워서 질문 게시판에서 힌트를 얻고 풀었습니다 힝