[백준] 10800 컬러볼

 

쉬운 문제라고 생각해서 풀었는데 틀렸다

그리고 계속 생각도 거꾸로해서 방법을 못떠올렸다

 

문제는 자기와 색이 다르고 나보다 작은공을 먹을 수 있다는 내용이다

 

문제를 보고 거꾸로 생각했다 

미리 합을 다 구해두고 크기를 기준으로 거꾸로 정렬해서

현재 나의 크기의 합들과 나의 색들의 합들을 빼야지했는데

두개의 교집합 부분을 다시 더해주기가 힘들어서 못했다

 

찾아보니 완전 거꾸로 생각하고있었다

반대로가면 쉽다

 

내가 여태까지 본 크기의 집합들과 색의 집합들을 가져가면 오히려 쉽다

크기를 기준으로 오름차순 정렬을하면 나는 다음 볼에 영향을 주는 볼이다

 

결국 생각해보면

현재 볼 = (여태까지의 합) - (같은 수의 크기 합) - ( 같은 크기의 크기 합) + 내크기

이렇게 하면 된다

 

집합이라고 생각하니 그림이 그려진다

 

근데 처리할게있다 이전게 나와 크기도 색도 같다면 답이 같아야한다!

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int C[200020],S[2020];
pair<pair<int, int>, int> arr[200020];
int ans[200020];
 
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        int w, c; scanf(" %d %d", &c, &w);
        arr[i] = { {w,c-1},i };
    }
    sort(arr, arr + n);
    int sum = 0;
    
    for (int i = 0; i < n; i++) {
        int weight = arr[i].first.first;
        int color = arr[i].first.second;
        int idx = arr[i].second;
 
 
        C[color] += weight;
        S[weight] += weight;
        sum += weight;
 
        ans[idx] = sum - C[color] - S[weight] + weight;
        if (i != 0 && weight == arr[i - 1].first.first && color == arr[i - 1].first.second) 
            ans[idx] = ans[arr[i - 1].second];
    }
    for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
}