2019 아주대학교 프로그래밍 경시대회 APC 기출문제

문제

세훈이는 선물가게를 운영한다. 세훈이의 선물가게는 특이하게도 손님이 어떤 선물을 구매할지 선택할 수가 없다. 대신 세훈이의 취향으로 랜덤하게 준비된 선물 중 몇 개를 구매할 것인지, 파란색과 빨간색 중 어떤 색으로 포장 받을 것인지만 결정해 주문할 수 있다.

상민이와 지수는 세훈이의 가게에서 선물 포장을 맡은 아르바이트생이다. 손님들은 파란색 포장지를 원하면 상민이에게, 빨간색 포장지를 원하면 지수에게 주문을 한다. 두 사람은 각자 주문을 받으면 그때부터 포장을 시작하는데, 현재 남아있는 선물 중 가장 앞에 있는 선물을 가져와 포장하고 주문을 받은 개수만큼 이를 반복하는 형태다. 이때 선물 하나를 포장하는 데 상민이는 A초, 지수는 B초가 걸린다. 두 사람 모두 받거나 밀린 주문이 없는데 미리 선물을 가져오거나 포장하는 일은 없으며, 두 사람이 동시에 선물을 가져올 때는 알바짬이 조금 더 있는 상민이가 먼저 가져오고, 지수가 그 뒤의 선물을 가져온다.

세훈이는 어제 구매한 선물이 망가져 있다는 항의 전화를 받았다. 자신이 준비한 선물에는 문제가 없었기에 손님에게 포장지의 색을 물었지만, 손님은 자신이 받은 선물이 무엇인지만 말하며 화를 낼 뿐이었다. 어쩔 수 없이 세훈이는 어제 가게를 방문한 손님들의 주문 내역을 보고 그 선물을 누가 포장했는지 파악하려 한다.

방문한 손님의 수와 각 손님이 주문한 시각, 선택한 포장지, 포장 받을 선물의 개수가 주어졌을 때 상민이와 지수가 각자 어떤 선물들을 포장했는지 알아내는 프로그램을 작성해보자.

입력

첫 줄에 상민이가 선물 하나를 포장하는 데 걸리는 시간 A, 지수가 선물 하나를 포장하는 데 걸리는 시간 B, 어제 세훈이 가게의 손님 수 N(1 ≤ N ≤ 1,000)이 주어진다.

이후 N개의 줄에 걸쳐 1번부터 N번 손님의 주문 시각 \(t_i\)(1 ≤ \(t_i\) ≤ 86,400), 선택한 포장지의 색깔 \(c_i\)(\(c_i\) = “B”|“R”), 주문한 선물의 개수 \(m_i\)(1 ≤ \(m_i\) ≤ 100)가 주어진다.

\(t_i\)는 가게가 오픈한 지 \(t_i\)초 후에 손님이 주문했음을 뜻하며 \(c_i\)는 포장지의 색깔을 의미하는 알파벳으로 “B”는 파란색을, “R”은 빨간색을 의미한다. 주어지는 입력은 시간의 흐름에 맞게 \(t_i\)의 오름차순으로 주어지며, 서로 같은 시간에 주문한 손님은 없다.

출력

첫 번째 줄에 상민이가 포장한 선물의 개수를 출력한다. 이후 두 번째 줄에 상민이가 포장한 선물들의 번호를 오름차순으로 공백으로 구분하여 출력한다.

세 번째 줄에 지수가 포장한 선물의 개수를 출력한다. 이후 네 번째 줄에 지수가 포장한 선물들의 번호를 오름차순으로 공백으로 구분하여 출력한다.

문제 원본에는 선물가게 포장 과정에 대한 상세한 그림이 있으니 참고

접근 과정

시간, 색상, 갯수, 선물번호 등 고려해야 할 값들이 많아 사용할 변수들과 자료구조를 정리하였다. 하나의 주문을 나타내는 구조체 order_t를 정의하였으며 주문이 순서대로 들어와서 순서대로 처리해야할 듯 싶어 주문 목록을 저장하는데 std::queue를 사용하였다. 마지막으로 스택처럼 사용할 수 있는 동적배열 std::vector 에 포장한 선물 번호 결과를 저장하기로 하였다.
저장한 주문에 대한 처리를 어떻게 할까 고민하였는데 최대로 포장해야 하는 선물 수가 1000 * 100개, 처리시간이 최대 300이므로 3백만 정도면 모든 시간대에 대한 포장 상태를 점검해도 괜찮겠다 싶어 매 \(t_i\)마다 주문과 포장을 처리하도록 구현하였다.
A에 대한 포장 처리와 B에 대한 포장 처리 구현이 겹쳐 pack()이라는 하나의 함수로 합쳐주었다. 끝내고보니 매개변수가 많아 저것도 그냥 하나의 구조체로 합쳐도 괜찮았을 것 같다.

소스 코드

#include <cassert>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef struct {
    int time;
    char color;
    int count;
} order_t;

int aSpeed, bSpeed;
int aCount, bCount;
int aRemain, bRemain;
int aAvailableTime, bAvailableTime;
vector<int> aResult, bResult;

int presentCount = 1;
int currentTime;

void pack(int& availableTime, int& remain, int& count, int speed, vector<int>& result) {
    if (currentTime < availableTime) {
        return;
    }

    while (remain != 0 && availableTime <= currentTime) {
        --remain;
        ++count;
        availableTime = currentTime + speed;
        result.push_back(presentCount++);
    }
}

int main(void) {
    int n;
    queue<order_t> orders;
    
    cin >> aSpeed >> bSpeed >> n;

    for (int i = 0; i < n; ++i) {
        int time, count;
        char color;

        cin >> time >> color >> count;
        orders.push(order_t{time, color, count});
    }

    order_t* order = &orders.front();
    while (orders.size() != 0 || aRemain != 0 || bRemain != 0) {
        if (order != nullptr) {
            assert(currentTime <= order->time);
            if (currentTime == order->time) {
                if (order->color == 'B') {
                    aRemain += order->count;
                } else {    // color == 'R'
                    bRemain += order->count;
                }
                orders.pop();

                if (orders.size() != 0) {
                    order = &orders.front();
                } else {
                    order = nullptr;
                }
            }
        }

        // 현재 시간에 맞는 포장 작업 수행
        pack(aAvailableTime, aRemain, aCount, aSpeed, aResult);
        pack(bAvailableTime, bRemain, bCount, bSpeed, bResult);

        ++currentTime;
    }

    // 결과 출력
    cout << aCount << endl;
    for (unsigned int i = 0; i < aResult.size(); ++i)
        cout << aResult[i] << ' ';
    cout << endl << bCount << endl;
    for (unsigned int i = 0; i < bResult.size(); ++i)
        cout << bResult[i] << ' ';

    return 0;
}