Baekjoon 17725번 세훈이의 선물가게

문제

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

걸린 시간

- 실패

풀이

C++

#include <iostream>
#include <vector>
#define MAX 30086400

using namespace std;

int main(){
    int a, b, n;
    cin >> a >> b >> n;
    int t, m;
    char c;
    vector<vector<int>> pack(2, vector<int>(MAX+1, 0));
    int at = 0, bt = 0; // current a, b time
    for(int i = 0; i < n; i++){
        cin >> t >> c >> m;
        if(c == 'B'){
            if(at < t) at = t;
            for(int j = 0; j < m; j++){
                pack[0][at]++;
                at += a;
            }
        }
        else{
            if(bt < t) bt = t;
            for(int j = 0; j < m; j++){
                pack[1][bt]++;
                bt += b;
            }
        }
    }
    vector<int> pa, pb; // pack a, b
    int gift = 1;
    for(int i = 0; i < MAX+1; i++){
        if(pack[0][i] && !pack[1][i]){
            for(int j = 0; j < pack[0][i]; j++){
                pa.push_back(gift);
                gift++;
            }
        }
        else if(!pack[0][i] && pack[1][i]){
            for(int j = 0; j < pack[1][i]; j++){
                pb.push_back(gift);
                gift++;
            }
        }
        else if(pack[0][i] && pack[1][i]){
            for(int j = 0; j < pack[0][i]; j++){
                pa.push_back(gift);
                gift++;
            }
            for(int j = 0; j < pack[1][i]; j++){
                pb.push_back(gift);
                gift++;
            }
        }
    }
    cout << pa.size() << "\n";
    for(int i = 0; i < pa.size(); i++)
        cout << pa[i] << " ";
    cout << "\n";
    cout << pb.size() << "\n";
    for(int i = 0; i < pb.size(); i++)
        cout << pb[i] << " ";
    return 0;
}

행을 상민이와 지수, 열을 시간으로 하는 2차원 배열에 포장한 선물의 개수를 저장했다.

시간은 손님의 수, 주문한 선물의 개수, 포장에 걸리는 시간 의 최대값을 모두 곱한 값 1,000 * 100 * 300 = 30,000,000 에 최대 주문 시각 86,400 을 더한 30,086,400 만큼의 크기를 할당해 주었다.

서브테스크 2 에서 여러번 틀렸습니다가 출력되었는데, 같은 시간에 상민이와 지수가 같이 포장을 하고 있을 경우의 처리가 문제였다.

상민이와 지수의 포장시간이 둘 다 0일 경우 상민이부터 번갈아가며 선물을 가져가 포장해야햐는지, 상민이가 모두 가져간 후 지수가 선물을 가져가는지 헷갈렸기 때문이었다.

문제의 조건에 서로 같은 시간에 주문한 손님은 없을 뿐더러, 포장시간이 0일 경우 주문과 동시에 모든 선물 포장이 끝난다는 조건이 있다. 때문에 같이 포장을 해야할 경우 무조건 상민이부터 모든 선물을 포장하도록 하면 해결되었다.