[BEAKJOON] 13335 - 트럭

이번 포스트에서 다뤄볼 문제는 Beakjoon online judge 사이트에 있는 13335번 문제 트럭을 풀어볼 예정이다.

밑에 글을 읽기에 앞서, 문제를 풀 때, 트럭 대신 버스라는 변수를 사용했다. 밑의 설명 또한 그렇게 진행하고자 한다. 오해 없길 바랍니다.

문제 레벨과 대충 훑어본 느낌으로는 매우 쉬운 문제였다.

문제를 보자마자 생각난 방법은 하나 있다.

1. 버스 라는 구조체를 만든다.
2. 그 구조체에서 다리를 구간별로 나눠서, 현재 버스가 다리 위에 어느 위치인지 기억하는 변수를 저장한다.

하지만, 이렇게 한다면, 매 초마다 각 버스의 위치를 1씩 증가 시켜줘야 한다. 즉, 시간 복잡도 면에서 n^2 이므로, 비효율적이다.

다른 방법을 생각해야만 했다.

우선, 아래의 입력과 출력 예제를 손으로 직접 따라가보며 확인해 보았다.

문제를 풀기 위해 생각해낸 방식이 빈공간에 0 을 넣는 방식이다.

시간	도착지				front	back	대기중인 버스
0							7	4	5	6
1						7	4	5	6
2					7		4	5	6
3				7		4	5	6
4			7		4	5	6
5		7		4	5		6
6	7		4	5		6
7	7	4	5		6
8	7	4	5	6

위와 같은 방식을 아래와 같이 하게 된다면, 매 초마다 하나씩 빼고, 하나씩 넣어주면 된다.

시간	도착지				front	back	대기중인 버스
0					0	0	7	4	5	6
1				0	0	7	4	5	6
2			0	0	7	0	4	5	6
3		0	0	7	0	4	5	6
4	0	0	7	0	4	5	6
5	0	7	0	4	5	0	6
6	7	0	4	5	0	6
7	7	4	5	0	6	0
8	7	4	5	6	0	0

단, 넣어줄 때, 최대하중을 넘어서는지 확인하고, 넘어서지 않는다면, 대기중인 버스에서 앞에 있는 버스가 들어가고,

넘어선다면, 0 을 넣어준다

 

코드는 밑에 있습니다.

#include <stdio.h>
#include <queue>
#define MAX 1000

using namespace std;

int bus[MAX];

void solution(int n, int w, int l);

int main(int argc, char const *argv[]) {
    /* code */
    int n, w, l;
    scanf("%d %d %d", &n, &w, &l);

    for (int i = 0; i < n; i++) {
        scanf("%d", bus+i);
    }

    solution(n, w, l);
    return 0;
}

void solution(int n, int w, int l) {
    queue<int> bridge;

    int acc = 0;
    int idx = 0;
    int time = 0;

    while (bridge.size() != w) bridge.push(0);

    while (idx != n) {
        acc -= bridge.front();
        bridge.pop();
        if (acc + bus[idx] <= l) {
            acc += bus[idx];
            bridge.push(bus[idx++]);
        } else {
            bridge.push(0);
        }
        time++;
    }

    int temp = 1;
    while (!bridge.empty()) { 
        if (bridge.front() == 0) {
            temp++;
        } else {
            time += temp;
            temp = 1;
        }
        bridge.pop();
    }

    printf("%d\n", time);
}

 

제가 겪은 시행착오에 대한 글입니다. 원하신다면 읽으시면 됩니다.

7 이 다리에 올라갔을 때, 뒤에 대기하는 트럭들은 다리위에 올라오지 못한다.
7 이 다리에서 벗어나기까지 걸리는 시간은 w+1 초 이다.

 

7 이 다리를 벗어나면서, 새로운 4 가 다리에 올라온다.
4 가 올라온 후, 1초 후에는 5 도 올라온다. 하지만, 그 뒤에 있는 6은 4, 5 와 같이 올라가지 못한다.
4 , 5 가 다리에서 벗어나고 나서야 6 이 올라온다.
4 , 5 가 다리에서 벗어나기 위해 걸리는 시간은 w+2 초 이다.

 

마지막으로 6 이 올라와서 벗어나기 위해 걸리는 시간은 w+1 초 이다.

하지만, 그룹이 내려가면서, 다른 그룹이 바로 올라오기 때문에, 그룹이 바뀌는 횟수만큼 빼준다.

 

문제에서 w 는 2이므로, 총 걸리는 시간은 8초이다.

 

이렇게 생각하다가 지난번 문제를 풀면서의 기억이 떠올랐다.

 

백준에서 주어진 예제를 믿지말자.

 

그래서 바로, 새로운 예제를 직접 만들어 보았다. 만들자마자 느꼈다. 무언가 잘못되었음을.

 

예제를 3개정도 만들어 보았는데, 위에 예제에서는 각 그룹이 유지가 된다.

어떤 말이냐면, 4,5 그룹이 전부 내려가기 전에 뒤에 대기하고 있던 버스은 올라오지 못하고 있다.

하지만, 뒤에 대기중인 버스가 무게가 6이 아닌, 4이하의 값이라면...

 

즉, 남은 5와 대기중인 버스의 하중의 합계가 최대하중 10 이하라면, 그룹이 다 내려가기 전에 그룹내에 맴버교체가 이뤄지게 되고, 위에서 생각했던 방식으로는 문제를 풀 수 없음을 알 수 있었다.

 

약 20분간 '에이, 그래도 조금만 손 보면 되겠지' 했지만, 손을 댈수록 망가져가는 코드를 볼 수 있었다.

그래서 손을 놓고, 잠시 산책을 갔다왔더니, 좋은 방법이 생각나 문제를 풀어냈다.