[백준 10800번] 컬러볼

[백준 10800번] 컬러볼

www.acmicpc.net/problem/10800

10800번: 컬러볼

 

 

 문제

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

공 번호색크기

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번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다.

 

 

 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
    int N;
    cin >> N;
    vector<pair<pair<int, int>, int>> v;
    for(int i=0;i<N;i++){
    	int a, b;
    	cin >> a >> b;
    	v.push_back(make_pair(make_pair(b, a), i));
    }
    
    sort(v.begin(), v.end());
    
    int c[200001] = {0,};
    int ans[200001] = {0,};
    int t = 0;
    for(int i=0;i<N;i++){
    	int ii = i;
    	while(ii < N && v[ii].first.first == v[i].first.first) ii++;
    	for(int j=i;j<ii;j++){
    		int size = v[j].first.first;
    		int color = v[j].first.second;
    		int idx = v[j].second;
    		ans[idx] = t - c[color];
    	}
    	
    	for(int j=i;j<ii;j++){
    		int size = v[j].first.first;
    		int color = v[j].first.second;
    		int idx = v[j].second;
    		c[color] += size;
    		t += size;
    	}

    	i = ii - 1;
    }
    
    for(int i=0;i<N;i++){
    	cout << ans[i] << '\n';
    }
	return 0;
}

 정렬해서 크기가 작은 것부터 누적 합, 색깔 별 누적합 각각 구하면서 푸는 문제였다. 처음에는 누적합을 사용하지 않고 구현했다가 시간초과를 받았고 누적합을 사용하여 구현은 쉽게 했는데 틀렸습니다를 받았다. 이유는 같은 size일 때의 처리때문이었다. 머리로는 이해가 잘 되는데 막상 구현하려고 하니 쉽지 않았고 작년 삼성 코테보다가 막혔던 그 기억이 다시 떠올랐다.

 매번 공에 대해 조사할 때 같은 크기의 공이 있는지 확인하고 점수 계산 먼저하고 나머지 누적합 처리를 해주면 된다. 꽤나 좋은 문제인 것 같다.