백준 10800번 컬러볼 c++ 풀이

문제

지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다.

공 번호색크기

1	1	10
2	3	15
3	1	3
4	4	8

이 경우, 2번 공은 다른 모든 공을 사로잡을 수 있다. 반면, 1번 공은 크기가 더 큰 2번 공과 색이 같은 3번 공은 잡을 수 없으며, 단지 4번 공만 잡을 수 있다. 

공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 출력하는 프로그램을 작성하시오. 

입력

첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N, 1 ≤ Si ≤ 2,000). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다.

출력

N개의 줄을 출력한다. N개의 줄 중 i번째 줄에는 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다.

예제 입력 1 복사

4
1 10
3 15
1 3
4 8

예제 출력 1 복사

8
21
0
3

예제 입력 2 복사

3
2 3
2 5
2 4

예제 출력 2 복사

0
0
0

 

 

사이즈 오름차순으로 정렬하고 지금까지의 모든 공의 합 - 현재 공과 같은 컬러의 무게 누적합 - 현재 공과 같은 사이즈의 무게 누적합 + 현재 공의 무게를 하게 된다면 현재 공의 정답을 구할 수 있다. 어려웠던 부분은 만약에 이전 공과 컬러와 사이즈가 모두 같다면 이전 공의 값과 같은 값을 가지도록 해야 하는 예외처리 부분이 어려웠다.

 

- c++ 풀이 / 참고 : https://tnwlswkd.tistory.com/100

#include <bits/stdc++.h>

#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;
}