[백준 BoJ] 10800 - 컬러볼

최종합 = 여태까지 더해진 값 - 색깔별 합 - 크기별 합  + 자신의 크기

문제를 지렁이 게임처럼 색깔이 다른 사이즈의 공을 흡수하는 것으로 오해하여 오래걸렸다. 그냥 단순하게 같은 색깔 전부 빼고, 같은 사이즈 전부 빼준 뒤 자신을 한번 더 더해주면 되는 문제였다. 자신을 한번 더해주는 이유는 자기 자신을 두번 뺄수는 없기 때문.

 

// https://www.acmicpc.net/problem/10800
// 컬러볼
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int cdp[200001], sdp[200001];
struct ball {
	int number, size, color, psum;
};
bool cmp(ball a, ball b) {
	if (a.size == b.size) return a.color < b.color;
	return a.size < b.size;
}
bool cmp2(ball a, ball b) {
	return a.number < b.number;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int N;
	cin >> N;
	vector<ball> balls(N);
	for (int i = 0; i < N; i++) {
		balls[i].number = i;
		cin >> balls[i].color >> balls[i].size;
	}

	sort(balls.begin(), balls.end(), cmp);
	
	int sum = 0;
	for (int i = 0; i < N; i++) {
		int curcolor = balls[i].color;
		int cursize = balls[i].size;

		cdp[curcolor] += cursize;
		sdp[cursize] += cursize;
		sum += cursize;
		balls[i].psum = sum - cdp[curcolor] - sdp[cursize] + cursize;
		if ( i!= 0 && balls[i].size == balls[i - 1].size && balls[i].color == balls[i - 1].color) {
			balls[i].psum = balls[i - 1].psum;
		}
	}
	
	sort(balls.begin(), balls.end(), cmp2);
	for (int i = 0; i < N; i++) {
		cout << balls[i].psum << "\n";
	}
}

• 누적 합