[백준/BOJ] 백준 10800번 : 컬러볼

www.acmicpc.net/problem/10800

10800번: 컬러볼

vector<pair<pair<int, int>, int>> ball에 ((크기,색),번호)를 한꺼번에 저장하고 정렬을 하여 크기 순으로 정렬한 뒤, int all_psum에 전체 누적합을 구하면서 vector<int> color_psum(200001, 0)에 각각 컬러의 누적합을 구해가며 문제를 해결했다. 

 

코드

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

int n;
vector<pair<pair<int, int>, int>> ball; //((크기,색),번호)를 한꺼번에 저장
vector<int> color_psum(200001, 0); //컬러별 누적합
int all_psum = 0; //전체 누적합
vector<int> result(200001);

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int c, s;

		cin >> c >> s;

		ball.push_back(make_pair(make_pair(s, c), i)); //공의((크기,색),번호)를 저장
	}

	//공을 크기 순으로 정렬
	sort(ball.begin(), ball.end());

	for (int i = 0; i < ball.size(); i++)
	{
		int this_ball_size = ball[i].first.first;
		int this_ball_color = ball[i].first.second;
		int this_ball_number = ball[i].second;

		int check_point = i - 1;
		int same_size_total = 0;

		//정렬상 같은 크기지만 앞에 있는것들 체크
		while ((check_point >= 0) && (ball[check_point].first.first == this_ball_size))
		{
			//같은 색깔일때
			if (ball[check_point].first.second == this_ball_color)
				check_point--;

			//다른 색깔일때
			else
			{
				same_size_total += ball[check_point].first.first;
				check_point--;
			}
		}

		//이전까지 전체 누적합 - 이전까지 다른색 이지만 같은 크기 것들 총합 - 이전까지 같은 색의 누적합
		result[this_ball_number] = all_psum - same_size_total - color_psum[this_ball_color];

		all_psum += this_ball_size;
		color_psum[this_ball_color] += this_ball_size;
	}

	for (int i = 1; i <= n; i++)
	{
		cout << result[i] << "\n";
	}

	return 0;
}