[BOJ] 10800번: 컬러볼

10800번: 컬러볼

풀이

지역본선 2015에서 초등부 4번, 고등부 2번으로 나왔던 문제다. 예전에 한 번 풀어본 적이 있었는데 무식하게

$O(n^2)$

으로 풀었다가 당연히 시간 초과를 맞았다 ㅋㅋ

우선 이건 내 머리에서 나온 풀이가 아니다. 사이즈 별로 정렬하는 것까진 생각했는데 색을 어떻게 처리해야 할 지 몰랐다. (왜 그랬는지 모르겠다)

CODER's BRUNCH님 블로그

그래도 지금은 완전히 이해했으니 정리하는 겸 써보겠다... N <= 200,000이나 되기 때문에

$O(n^2)$

으론 불가능하다.

$O(nlogn)$

우선, 공 크기 별로 오름차순 정렬 한다.

(s[j] < s[i]를 만족하는 최대 j에 대해 s[1..j]의 누적합) - (c[k] = c[i]이고 k < i인 s[k]의 누적합)이 i번째 플레이어가 잡을 수 있는 모든 공들의 크기 합이다.

코드

#include <bits/stdc++.h>
using namespace std;

const int MN = 200000 + 1;
int N, accul, colorSum[MN], ret[MN];

struct Ball
{
    int c, s, idx;
} ball[MN];
bool COMP(const Ball &a, const Ball &b) { return a.s < b.s; }

int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d %d", &ball[i].c, &ball[i].s);
        ball[i].idx = i;
    }
    sort(ball, ball + N, COMP);
    for (int i = 0, j = 0; i < N; ++i)
    {
        for (; ball[i].s > ball[j].s; ++j)
        {
            accul += ball[j].s;
            colorSum[ball[j].c] += ball[j].s;
        }
        ret[ball[i].idx] = accul - colorSum[ball[i].c];
    }
    for (int i = 0; i < N; ++i)
        printf("%d\n", ret[i]);
    return 0;
}