8189

static int N, A, B, msgs[1001];
static queue<int> q[2];
 
static void solution(void)
{
    int last, cnt = 0, rmv;
    scanf("%d %d %d", &N, &A, &B);
     
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &last);
        q[0].push(last);
        msgs[last] = 1;
    }
 
    for (int t = 1; !q[0].empty(); t++)
    {
        if (t <= 1000)
        {
            cnt += msgs[t];
            msgs[t] = 0;
        }
         
        if (cnt >= A || t - q[0].front() == B)
        {
            rmv = cnt / 2 + cnt % 2;
            cnt -= rmv;
 
            for (int i = 1; i <= rmv; i++)
            {
                q[1].push(t);
                q[0].pop();
            }
        }
    }
 
    while (!q[1].empty())
    {
        printf("%d ", q[1].front());
        q[1].pop();
    }
    puts("");
}

이번 문제는 큐를 사용하면 쉽게 풀리는 것 같다.

먼저 msgs 에서는 해당 인덱스에 해당 하는 시간에 들어온 편지가 있는지 여부를 저장한다.

그래서 두번째 for문에서는 시간이 1 부터 모든 편지함이 빌 때 까지 반복을 하게 된다.

또 중요한 점이 t는 배열의 인덱스르도 사용되기 때문에 범위 조건을 반드시 명시하여야 한다는 점이다.

(이를 간과하고 있어서 런타임 에러가 발생하였다.)

 

그래서 시간이 계속 흐르면서 문제에서 언급한 조건이 되었을 때 조건대로 편지를 비우게 되고, 그 시간을 다른 큐에 저장하여 이 후에 정답으로 사용하는 것이다.

 

한가지 좀 특이한 점은 편지함에서 제거할 개수를 정하는 것인데,

cnt / 2 + cnt % 2 라는 것이다. 

 

이에 대해서는 cnt가 1일 때를 생각해보면 납득이 된다. 마지막으로 남은 편지의 개수가 하나이고, 그 편지를 받고 B만큼의 시간이 지났는데, cnt / 2로 계산하게 되면 0이 되어 편지를 비울 수 없다.

이에 대한 처리로 보면 되겠다.