백준 10800 컬러볼

백준 10800 ←클릭

변수 설정

total : 현재까지 모두 더한 전체 공의 무게 합
now_total :자신보다 작은 전체 공의 무게 합 + 자신의 무게
c_arr[color] : 현재까지 특정 color에 대한 모든 무게 합

아이디어

• 공들을 무게와 색을 기준으로 오름차순
• 먹을 수 있는 공의 총 무게= now_total - c_arr[color]
• 만약 자신과 같은 색과 무게의 공을 계산한 적이 있으면 해당 값 사용

코드

github

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
int N;
bool print = false;
int c_arr[200001] = { 0, };
int total = 0;
int now_total = 0;
bool visited_size[2001];
int ans[200001];


struct ball {
	int idx;
	int b_color;
	int b_size;
};
struct comp {
	bool operator()(ball& a, ball& b) {
		if (a.b_size == b.b_size) return a.b_color < b.b_color;
		return a.b_size < b.b_size;
	}
};

ball pq[200001];



int main() {
	constexpr auto endl{ '\n' };
	cin.tie(nullptr);

	freopen("input/10800_input.txt", "r", stdin);
	cin >> N;


	for (int i = 0; i <= 2000; i++) {
		visited_size[i] = false;
	}
	
	for (int i = 0; i < N; i++) {
		int left, right;
		cin >> left >> right;
		ball b;
		b.idx = i;
		b.b_color = left;
		b.b_size = right;
		pq[i] = b;
	}
	sort(pq, pq + N, comp());
	for(int i = 0 ; i < N ; i++) {
		ball top = pq[i];
		int color = top.b_color;
		int size = top.b_size;
		int index = top.idx;

		total += size;
		if (!visited_size[size]) {
			now_total = total;
		}//처음 방문하는 사이즈에 대해서는 update
		visited_size[size] = true;
		c_arr[color] += size;
		if(print) cout << "total: " << total << " now_total: " << now_total << " color: " << color << " c_arr: " << c_arr[color] << " size:" << size  << endl;
		if(print) cout << now_total - c_arr[color] << endl;
		if (i != 0 && (pq[i - 1].b_color == color) && (pq[i - 1].b_size == size)) ans[index] = ans[pq[i - 1].idx];
		else ans[index] = now_total - c_arr[color];
	}
	for (int i = 0; i < N; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

비고

색과 무게 모두 똑같은 공이 있는 경우를 예외처리 하기 위해 comp함수에 색을 기준으로도 오름차순 하게끔 해야함..

그리고

	constexpr auto endl{ '\n' };
	cin.tie(nullptr);

위의 코드를 사용하지 않으면 시간 초과가 남