[BOJ/Gold 3] 백준 2065 나룻배(C++)

문제 링크

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

2065번: 나룻배

 

문제

강을 사이에 두고 위치한 두 정박장 사이를 한 대의 나룻배가 오가고 있다. 두 정박장은 강을 기준으로 왼쪽(left), 오른쪽(right)으로 구분한다. 제일 처음에는 나룻배가 왼쪽 정박장에 위치해 있다. 이 나룻배는 한번에 최대 M명의 사람을 태울 수 있으며, 한 쪽 정박장에서 다른 쪽 정박장으로 이동하는데 양쪽 방향 모두 t만큼의 시간이 걸린다. 나룻배는 손님을 한 쪽 정박장에서 다른 쪽 정박장으로 실어 나르며 두 정박장 사이를 움직인다.

나룻배가 어떤 정박장에 도착하게 되면, 그 정박장으로 가고자 하는 사람들을 우선 모두 내려준다. 그 다음에는, 그 정박장에서 기다리고 있던 손님들을 배에 태울 수 있는 데까지 태운다. 손님이 배에 타는데 드는 시간은 없다고 가정하며, 가장 오래 기다린 사람이 먼저 배를 타게 된다. 손님을 다 태운 후에는 반대쪽 정박장으로 이동하게 된다. 만약 기다리던 손님이 없다면, 나룻배가 그 정박장에서 다음 손님을 기다리게 된다. 만약 기다리던 중 반대 쪽 정박장에 손님이 도착하면, 그 쪽 정박장으로 이동하게 된다.

각각의 손님들이 어느 정박장에 언제 도착하는지에 대한 정보가 주어질 때, 각 손님들이 원하는 곳에 도착하게 되는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 M, t, N이 주어진다. 다음 N개의 줄에는 각각의 손님이 정박장에 도착하는 시간과 도착하는 정박장의 위치가 주어진다. 손님이 정박장에 도착하는 시간은 10만 이하의 음이 아닌 정수이다.

출력

N개의 줄에, 입력받은 순서대로 각 손님이 목적지에 도착하게 되는 시간을 출력한다.

제한

• 1 ≤ M ≤ 10,000
• 1 ≤ t ≤ 10,000
• 1 ≤ N ≤ 10,000

예제 입력 1

2 10 10
0 left
10 left
20 left
30 left
40 left
50 left
60 left
70 left
80 left
90 left

예제 출력 1

10
30
30
50
50
70
70
90
90
110

예제 입력 2

2 10 3
10 right
25 left
40 left

예제 출력 2

30
40
60

알고리즘 분류

• 구현
• 자료 구조

풀이

정박장을 구현할 큐 2개를 선언해야 한다. 0번째 큐는 왼쪽 정박장이며 1번째 큐는 오른쪽 정박장이다.

또한 입력받은 순서대로 각 손님이 목적지에 도착하는 시간을 출력해야 하므로, 손님들의 입장 시간과 정박장을 따로 기록해두고, 큐에는 손님들의 번호를 push한다.

시작 시간은 0이며, 정박장의 번호는 왼쪽 정박장에서 출발하기 때문에 0이다.

먼저 시작하기 전에 

경우의 수는 다음과 같다.

• 현재 큐가 비어있지 않은 경우
  • 현재 큐에서 현재 시간까지 입장했던 손님들을 앞에서부터 최대 M명까지 데려가고, 이 M명의 도착 시간은 현재 시간에서 T만큼을 더한 시간으로 기록한다.
  • 만약 데려갈 손님이 없다면, 경우의 수는 2가지이다.
    • 반대쪽 정박장에 입장할 손님이 없다면, 현재 정박장에서 손님이 들어올 때까지 계속 기다린다.
    • 반대쪽 정박장에 입장할 손님이 있다면, 두 정박장에 가장 먼저 들어올 손님의 입장 시간을 비교해 입장 시간이 더 빠른 손님이 입장할 정박장으로 이동하거나 가만히 있는다.
• 현재 큐가 비어있는 경우
  • 현재 위치한 정박장에서는 더 이상 데려갈 손님이 없으므로, 반대쪽 정박장에서 가장 먼저 대기하고 있는 사람의 입장한 시간에서 현재 시간을 뺀 만큼 기다린 후 반대쪽 정박장으로 이동한다. 만약 현재 시간보다도 빨리 도착했었다면 바로 이동한다.

이것을 양쪽 큐가 전부 빈 상태가 될 때까지 반복한 후 입장 순서에 따라 손님들의 도착 시간을 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 10001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int M, T, N, A;
string B;
vector<pair<int, string> > Vec;
queue<int> Q[2];
int Answer[MAX];

void input() {
    cin >> M >> T >> N;
    for (int i = 0; i < N; i++) {
        cin >> A >> B;
        Vec.push_back(make_pair(A, B));
        if (B == "left") {
            Q[0].push(i);
        }
        else {
            Q[1].push(i);
        }
    }
}

void settings() {
    int Now = 0;
    int Where = 0;
    while (1) {
        if (Q[0].empty() && Q[1].empty()) {
            break;
        }
        int People = M;
        bool Flag = false;
        if (!Q[Where].empty()) {
            while (People--) {
                if (!Q[Where].empty()) {
                    if (Vec[Q[Where].front()].first <= Now) {
                        Answer[Q[Where].front()] = Now + T;
                        Q[Where].pop();
                        Flag = true;
                    }
                    else {
                        break;
                    }
                }
                else {
                    break;
                }
            };
            if (Flag) {
                Now += T;
                Where = !Where;
            }
            else {
                if (!Q[!Where].empty()) {
                    if (Vec[Q[Where].front()].first <= Vec[Q[!Where].front()].first) {
                        Now += max(0, (Vec[Q[Where].front()].first - Now));
                    }
                    else {
                        Now += (T + max(0, (Vec[Q[!Where].front()].first - Now)));
                        Where = !Where;
                    }
                }
                else {
                    Now += max(0, (Vec[Q[Where].front()].first - Now));
                }
            }
            
        }
        else {
            if (!Q[!Where].empty()) {
                Now += (T + max(0, (Vec[Q[!Where].front()].first - Now)));
                Where = !Where;
            }
        }
    };
}

void find_Answer() {
    for (int i = 0; i < (int)Vec.size(); i++) {
        cout << Answer[i] << "\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}