[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번째 트럭의 무게를 나타낸다.

 

 

출력

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

 

 

해결 방법

이 문제의 핵심 아이디어는 다음 3가지이다.

1️⃣ 다리 = 크기가 w로 제한되어있는 큐
2️⃣ 최대하중을 초과하는 트럭은 다리에 올라올 수 없게하는 투명 트럭 올리기
3️⃣ 모든 트럭(투명 트럭 포함)이 다리에 처음 올라올때만 시간 += 1

 

현재 다리 위에 있는 트럭의 무게 합인 weightSum 변수를 선언하고 첫 번째 트럭부터 차례대로 탐색하면 되는데

만약 큐의 사이즈가 w라면(다리에 다른 트럭이 올라갈 수 X) 맨 앞의 트럭은 다리를 빠져나갈 때가 됐다는 뜻이므로 맨 앞의 원소를 제거하고 weightSum에서 이 원소의 무게를 빼준다.

그리고 weightSum에 다음 트럭의 무게를 더한 값이 L보다 작거나 같다면 다음 트럭이 다리에 올라올 수 있다는 뜻이므로 큐에 이 트럭을 추가하고 weightSum에도 이 트럭의 무게를 더해준다.

그런데 만약 weightSum에 다음 트럭의 무게를 더한 값이 L보다 크다면 이 값이 L보다 작아질 때까지 기다려야 한다.

나는 큐에 0을 계속 삽입해서 다음 트럭이 빠져나가지 못하게 하는 방식으로 구현했다.

 

예를 들어, 다리 길이가 2이고 트럭의 무게가 [7, 4, 5, 6]인 경우

다리에 7이 올라가면 큐 = [7], weightSum = 7, ans = 1이다.

다음으로, 4가 올라가야 하는데 7 + 4 > 10(L)이므로 큐에 0을 삽입하면 큐 = [7, 0], ans = 2이다.

이제 큐의 사이즈 = 2 이므로 맨 앞의 트럭인 7을 제거하면 큐 = [0], weightSum = 0이다.

이제 4가 올라갈 수 있기 때문에 큐에 4를 삽입하면 큐 = [0, 4], weightSum = 4, ans = 3이다.

또 큐의 사이즈가 2가 됐으므로 맨 앞의 0을 제거하면 큐 = [4]가 된다.

4+ 5 < 10(L)이므로 큐에 5를 삽입하면 큐 = [4, 5], weightSum = 9, ans = 4이다.

다시 큐의 사이즈가 2이므로 4를 제거하면 큐 = [5], weightSum = 5가 된다.

5 + 6 > 10(L)이므로 5가 빠져나갈 때까지 6은 올라갈 수 없다. 그래서 큐에 0을 삽입하면 큐 = [5, 0], ans = 5이다.

다시 큐의 사이즈가 2이므로 맨 앞의 트럭을 제거하면 큐 = [0], weightSum = 0이 된다.

0 + 6 < 10(L)으로 6을 큐에 삽입하면 큐 = [0, 6], weightSum, = 6, ans = 6이다.

마지막 트럭까지 다리에 올리고 나면 반복문이 종료되는데 마지막 트럭이 다리에서 완전히 빠져나가는 시간을 추가로 더해줘야 하기 때문에 최종 답은 ans + (다리 길이) = 6 + 2 = 8이 된다.

 

 

유사 문제

프로그래머스 [42583] 다리를 지나는 트럭

 유사한 수준이 아니라 그냥 똑같은 문제. 데이터 크기만 다르다.

 

 

내 코드

// [13335] 트럭
// 구현, 시뮬레이션, 큐
#include <iostream>
#include <queue>
using namespace std;
 
int n, w, L, ans, a[1000];
queue<int> q;
 
void input()
{
    cin >> n >> w >> L;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
}

void solution()
{
    int weightSum = 0; // 다리 위의 트럭 무게의 합
    for(int i = 0; i < n; i++) {
        while(true) {
            if(q.size() == w) {
                weightSum -= q.front(); // 맨 앞의 트럭 제거
                q.pop();
            }
            if(a[i] + weightSum <= L) {
                break;
            }
            q.push(0); // 무게가 L을 넘는 경우
            ans++;
        }
        q.push(a[i]);
        weightSum += a[i];
        ans++;
    }
}

int main()
{
    input();
    solution();
    cout << ans + w; // 마지막 트럭이 건너는 시간(W) 추가
    return 0;
}