[백준]10800번. 컬러볼

[문제]

 

www.acmicpc.net/problem/10800

10800번: 컬러볼

 

[풀이]

 

각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 구하는 문제이다.

단 공의 색깔이 같거나 공의 크기가  같다면 잡을 수 없다.

 

처음에 단순 이중 for문을 사용해서 풀려고 했다. 그러면 시간 복잡도가 O(N^2)이 된다.

하지만 N의 범위가 1 ≤ N ≤ 200,000 이므로 최악의 경우 시간초과가 발생한다.

 

따라서 다른 방법을 생각했다.

먼저 공의 크기를 기준으로 오름차순 정렬을 하고 , 현재까지의 모든 공의 크기 합에서 색깔이 같거나 크기가 같은 공의 무게를 빼준다.

 

(idx)번째 공이 사로잡을 수 있는 공의 크기

= 현재까지 공 크기의 합 - (idx)번째 공과 색깔이 같은 공들의 무게 합 - (idx)번째 공과 크기가 같은 공들의 무게 합 + (idx)번째 공의 무게

 

단 , 위의 식에서 크기와 색깔이 모두 같은 경우 이전 index의 공이 사로잡을 수 있는 값과 같도록 하였다.  

 

또한 오름차순 정렬을 할 때 , 공의 크기가 같다면 색깔을 기준으로 정렬하도록 하였다.

색깔을 신경쓰지 않으면 아래와 같은 문제가 발생한다.

 

Ex)

3

1 4

2 4

1 4

 

출력 : -4

정답 : 4 

 

[코드]

 

시간 : 208ms

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 200020

using namespace std;

struct ball{
    int weight, color, idx;
};

int ans[MAX]={0,};
int C[MAX]={0,};
int S[MAX]={0,};
int N;
bool comp(ball &a, ball &b) {

    if (a.weight==b.weight) return a.color < b.color;

    return a.weight < b.weight;
}
int main(void)
{
    vector <ball> v;

    cin >> N;
    for(int i=0;i<N;i++){
        int weight,color;
        cin >> color >> weight;
        v.push_back({weight,color,i});
    }
    sort(v.begin(),v.end(),comp);
    
    int sum=0;
    
    for(int i=0;i<N;i++){
        
        int weight = v[i].weight;
        int color = v[i].color;
        int idx = v[i].idx;
        
        C[color]+=weight;
        S[weight]+=weight;
        sum+=weight;
        
        ans[idx]= sum - C[color] - S[weight] +weight;
        if(i!=0 && (v[i-1].color == color) && (v[i-1].weight == weight))    ans[idx] = ans[v[i-1].idx];
    }
    
    for(int i=0;i<N;i++)    cout << ans[i] <<"\n";
    return 0;
}