[Algorithm] Baekjoon 10800번 : 컬러볼

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

10800번: 컬러볼

struct Node
{
    int num;
    int color;
    int size;
};
 
int n;
vector<Node> balls;
int sumColor[200001] = { 0 };
int sumSize[2001] = { 0 };
int answers[200001] = { 0 };
 
bool cmp(const Node& a, const Node& b)
{
    if (a.size == b.size)
    {
        return a.color < b.color;
    }
 
    return a.size < b.size;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        int color, size;
        cin >> color >> size;
 
        balls.push_back({ i,color,size });
 
    }
 
    sort(balls.begin(), balls.end(), cmp);
    int sum = 0;
    int prevSize = -1;
 
    for (int i = 0; i < balls.size(); ++i)
    {
        int curNum = balls[i].num;
        int curColor = balls[i].color;
        int curSize = balls[i].size;
 
        sum += curSize;
        sumColor[curColor] += curSize;
        sumSize[curSize] += curSize;
 
        answers[curNum] = sum - sumColor[curColor] - sumSize[curSize] + curSize;
        if (i > 0 && curColor == balls[i - 1].color && curSize == balls[i - 1].size)
        {
            answers[curNum] = answers[balls[i - 1].num]; // 계승
        }
    }
 
    for (int i = 1; i <= n; ++i) printf("%d\n", answers[i]);
}

문제설명은 굉장히 심플하다. 

각 공마다 색깔이 다르면서 자기보다 작은 공들의 합을 구하는 문제인데 N이 20만이다.

당연히 완전탐색으로는 20만 ^ 20만 => 400억이라 안된다.

 

풀이방법으로는 다음과 같다.

일단 크루스칼을 풀이하는것마냥 크기를 기준으로 오름차순 정렬을 한다. 그리고 일단 값을 계속 누적시킨다.

그리고 각 사이즈마다, 색깔마다도 값을 누적시킨다. 그러면 현재 차례(번호)까지 각 사이즈와 컬러마다 값이 얼마나 누적됐는지를 알 수 있고, 현재누적값에다가 현재컬러의 누적값, 현재크기의 누적값을 빼주고 다시 자기 크기값을 더해준다.

 

단, 만약 이전 번호의 공과 크기와 색깔이 같으면 그 값을 그대로 계승한다.(이건 이해가 쉽게 될거라 생각한다)

그러면 이것 이외의 공식인 현재누적값 - 컬러누적값 - 크기누적값 + 현재크기  <-- 이게 왜 되는가??

 

일단 간단하게 접근하면 같은색깔의 공은 포함을 못하니 컬러누적값을 빼준것이고, 크기또한 자기보다 같거나 크면 안되는데 처음에 크기기준으로 오름차순을 했기 때문에 현재까지 자기보다 작거나 같은크기는 있었을지언정, 큰것은 없다.

그렇다면 같은크기였던것들만 빼주면 되기 때문에 크기누적값을 따로 저장했던 것이고 빼주는 것이다.

현재크기를 더해주는것은 해당 공식을 수행하기전에 각 누적값들에 다 누적했던것들이니까 다시 더해주는것이고...

 

이렇게 말하면 '컬러누적값 뺴버리고 크기누적값 빼버려도 되나? 중복해서 빼버린게 있지않을까?' 할 수 있다. 당연히 중복되고, 그렇기 때문에 더 일찍이 말했듯이 이전 번호의 공과 '크기와 색깔'이 같을 때 그대로 계승하는 것이다.

 

사실 컬러별로 누적시키는것까지는 자연스럽게 생각이 됐는데, 이후에 틀렸다가 나오면서 코드가 점점 지저분해지길래 뭔가 놓친게 있다고 판단해서 다른 풀이를 참고했다.. 크기별로 누적시키는것까지는 생각 못했었고, 해당부분에 대한걸 여러 조건문 걸다보니 지저분해졌었는데.. 그래도 이해는 하고 넘어가서 다행이다.