[BOJ/Gold 5] 백준 22234 가희와 은행(C++)

문제 링크

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

22234번: 가희와 은행

 

문제

가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다.

 

[그림 1] 카운터 직원과 N명의 손님

x번 손님에 대한 정보는 x번 손님의 id 값인 Px와 업무를 처리하는 데 필요한 시간인 tx초로 정보가 주어지게 됩니다.

은행이 영업을 시작하고 난 후에 들어오는 손님은 M명 있습니다. 이 손님들은 입력을 받은 순서대로 각각 N+1, N+2, ..., N+M번 손님이 됩니다.

이 손님들에 대한 정보는 x번 손님의 id 값인 Px와 업무를 처리하는 데 필요한 시간인 tx초, 영업 시작 cx초 후에 들어왔다는 정보가 주어지게 됩니다.

손님은 은행에 들어옴과 동시에, 대기 큐의 맨 뒤에 서게 됩니다. N+1번 손님이 은행을 영업을 시작하고 cN+1초 후에 들어왔다고 생각해 보겠습니다.

 

[그림 2] 은행이 영업을 시작하고 cN+1초 후 상황

N+1번 손님은 은행에 들어오자 마자 대기 큐의 맨 뒤에 줄을 서게 되므로, 영업을 시작하고 cN+1초 후에 대기 큐의 상태는 위와 같습니다.

창구에 있는 직원과 고객들은 아래와 같은 알고리즘으로 업무를 처리합니다.

1. 대기 큐의 맨 앞에 있는 고객이 x번 손님이라고 하면, 창구에 있는 직원은
   • tx가 T보다 크다면, x번 손님의 업무를 T초동안 처리합니다. 그 후, x번 손님의 업무가 끝나는 데 필요한 시간인 tx는 T만큼 감소합니다.
   • 그렇지 않으면, x번 손님의 업무를 tx초 동안 처리합니다. 이후에, x번 손님의 업무가 끝나는 데 필요한 시간인 tx는 은 0이 됩니다.
2. 대기 큐의 맨 앞에 있는 고객인 x번 손님은
   • 업무가 끝나는 데 필요한 시간인 tx가 0이 되었다면, 은행 바깥으로 나가게 됩니다.
   • 그렇지 않으면 대기 큐의 맨 뒤로 이동하게 됩니다. 만약에 이 때 도착한 손님이 있다면, 도착한 손님 뒤로 가게 됩니다.
3. 대기 큐에 고객이 남았다면 1로 돌아갑니다.

은행이 영업을 시작할 때 부터 창구에 있는 직원은 일을 시작합니다.

은행이 영업을 시작한 시점으로부터 0초가 지났을 때 부터 W-1초가 지날 때 까지 창구에 있는 직원이 어떤 고객의 업무를 처리하는지 알려주세요.

입력

첫 번째 줄에 N과 T, W가 공백을 구분으로 해서 주어집니다.

두 번째 줄 부터 N개의 줄에는 0초일 때, 대기 큐의 앞에 있는 고객부터, Px와 고객이 일을 처리하는 데 필요한 시간 tx가 공백으로 구분되어 주어집니다.

N+2번째 줄에는, 1초 이후에 은행에 들어온 고객 수 M이 주어집니다.

N+3번째 줄부터 M개의 줄에 걸쳐서, Px, tx, cx가 공백으로 구분되어 주어집니다. 입력된 순서대로 각각 N+1, ..., N+M번 고객입니다.

이는 고객 id가 Px인 고객은 일을 처리하는 데 필요한 시간이 tx초이고, 영업 시작 시간으로부터 cx초가 지났을 때 은행에 들어왔다는 것을 의미합니다.

출력

i번째 줄에는 은행이 영업을 시작한 시점으로부터 i-1초가 지났을 때 은행 직원이 처리하고 있는 고객 id를 출력해 주세요.

제한

• N, T, W, M는 구간 [1, 2×105]에 속하는 정수입니다.
• 0초부터 W-1초까지 모든 순간에 대기 큐가 비어 있는 경우는 존재하지 않습니다.
• 고객이 일을 처리하는 데 걸리는 시간은 구간 [1, 109]에 속하는 정수입니다.
• 고객 id는 구간 [1, 109]에 속하는 정수이고, 중복되지 않습니다.
• [N+1, N+M]에 속하는 임의의 정수 x에 대해, cx는 구간 [1, 109]에 속하는 정수이며, 중복되지 않습니다.
  즉, 영업을 시작하고 난 후에는 같은 시간에 2명 이상이 동시에 들어오지 않습니다.

예제 입력 1

1 5 7
1 6
1
3 1 5

예제 출력 1

1
1
1
1
1
3
1

[그림 3] 예제 1번 상황의 처음 대기 큐

처음에 대기 큐에는 id가 1인 1번 손님만 있었습니다. T가 5이므로, 5초 동안 고객 1번의 업무를 처리합니다.

영업을 시작하고 나서 5초 후에, id가 3인 2번 손님이 들어오게 됩니다. 그와 동시에 1번 손님은 대기 큐의 맨 뒤로 가게 됩니다.

대기 큐의 맨 뒤로 가는 id가 1인 1번 손님은, 은행에 들어온 id가 3인 2번 손님의 뒤로 가게 됩니다.

 

[그림 4] 5초가 지난 후 예제 1의 대기 큐

id가 3인 손님이 업무를 마치는 데 필요한 시간 1초는 T값인 5초 보다 작거나 같으므로, 카운터의 직원은 1초 동안 2번 손님의 업무를 처리합니다.

 

[그림 5] 6초가 지난 후 예제 1의 대기 큐

다음에, 6초일 때, id가 1인 손님의 일을 처리하게 됩니다.

예제 입력 2

1 3 10
1 6
2
3 4 5
2 4 2

예제 출력 2

1
1
1
2
2
2
1
1
1
3

알고리즘 분류

• 구현
• 자료 구조

풀이

먼저 N명의 손님을 큐에 push하고, M명의 손님을 벡터에 push해놓는다.

그리고 큐가 비거나 W초가 지날 때까지, 매 초마다 어떤 손님을 받는지 출력해준다.

큐의 front에 있는 손님의 업무 처리에 필요한 시간이 T보다 크다면, T초 동안 매 초마다 해당 손님의 번호를 출력해주며, 벡터에 push해놓은 다른 손님들의 입장 시각과 현재 시각이 일치하면 해당 손님을 큐에 push해준다.

현재 손님의 업무 처리에 필요한 시간이 T보다 작다면, 해당 시간 동안 매 초마다 손님의 번호를 출력해주며, 마찬가지로 벡터에 push해놓은 다른 손님들의 입장 시각과 현재 시각이 일치하면 해당 손님을 큐에 push해준다.

W초 동안 큐가 비어 있는 경우는 없기 때문에, 현재 시각이 W초가 되면 반복문을 종료한다.

코드

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

using namespace std;
struct INFO {
    int P, T;
};

int N, T, W, M;
queue<INFO> Q;
vector<pair<INFO, int> > Vec;
int Now = 0;

bool compare(pair<INFO, int> A, pair<INFO, int> B) {
    return (A.second < B.second);
}

void input() {
    cin >> N >> T >> W;
    for (int i = 0; i < N; i++) {
        int P, T;
        cin >> P >> T;
        Q.push({ P,T });
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        int P, T, C;
        cin >> P >> T >> C;
        INFO I = { P,T };
        Vec.push_back(make_pair(I, C));
    }
    sort(Vec.begin(), Vec.end(), compare);
}

void find_Answer() {
    while (!Q.empty()) {
        int NowP = Q.front().P;
        int NowT = Q.front().T;
        Q.pop();

        if (NowT > T) {
            for (int i = 0; i < T; i++) {
                cout << NowP << "\n";
                Now++;
                if (Now == W) {
                    return;
                }
                if (Vec[0].second == Now) {
                    Q.push({ Vec[0].first.P,Vec[0].first.T });
                    Vec.erase(Vec.begin());
                }
            }
            Q.push({ NowP,NowT - T });
        }
        else {
            for (int i = 0; i < NowT; i++) {
                cout << NowP << "\n";
                Now++;
                if (Now == W) {
                    return;
                }
                if (Vec[0].second == Now) {
                    Q.push({ Vec[0].first.P,Vec[0].first.T });
                    Vec.erase(Vec.begin());
                }
            }
        }
    };
}

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

    return 0;
}