[C++] 백준 10800번 컬러볼

구조체를 이용해서 공과 색에 대한 값을 저장합니다.

ball = 공의 인덱스, 색, 사이즈, 합한값을 저장합니다.
colorSize = 현재까지 최대 사이즈, 현재 모두 더한 누적값, 이전 최대 사이즈
colorSize에 이전 최대 사이즈의 경우는 사이즈가 같을 경우 누적되기 전의 값이 입력되어야 하기 때문입니다.

ball을 size 오름차순으로 정렬을 해주고
colorSize에 각 색의 누적값을 쌓아갑니다.

현재 최대값과 비교해서 더 클 경우
(누적된 값) - (현재 색)의 누적 값을 입력합니다.

현재 최대값과 비교해서 같을 경우
(누적되기 이전의 값) - (현재 색의 누적되기 이전의 값)을 계산해서 입력합니다.

모든 공에 대한 입력이 끝났으면 ball에 대해서 숫자를 기준으로
정렬을 해준뒤 차례대로 출력해줍니다.

 

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

struct ball {
	int num;
	int color;
	int size;
	int sum;
};

struct colorSize {
	int size;
	int sum;
	int before;
};

bool cmp(const ball& a, const ball& b) {
	return (a.size < b.size);
}

bool cmp2(const ball& a, const ball& b) {
	return (a.num < b.num);
}

int main(int argc, char *argv[]) {
	int N;
	int before = 0;
	int sum = 0;
	
	cin >> N;

	vector<ball> b(N);
	vector<colorSize> cs(N);

	for (int i = 0; i < N; ++i) {
		b[i].num = i;
		cin >> b[i].color >> b[i].size;
	}

	sort(b.begin(), b.end(), cmp);

	for (int i = 0; i < N; ++i) {
		int index = b[i].color - 1;

		if (i > 0 && b[i].size > b[i - 1].size) {
			before = sum;
		}

		sum += b[i].size;

		if (b[i].size > cs[index].size) {
			cs[index].size = b[i].size;
			cs[index].before = cs[index].sum;
		}
		cs[index].sum += b[i].size;

		if (i > 0 && b[i].size > b[i - 1].size) {
			b[i].sum = sum - cs[index].sum;
		}
		else if (i > 0 && b[i].size == b[i - 1].size) {
			b[i].sum = before - cs[index].before;
		}
	}

	sort(b.begin(), b.end(), cmp2);

	for (int i = 0; i < N; ++i) {
		cout << b[i].sum << '\n';
	}

	return 0;
}