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

https://www.acmicpc.net/problem/10800

10800번: 컬러볼

 

1. 접근

공에 대한 구조체로 벡터 배열을 만들고 크기 순으로 정렬한 뒤

반복문을 통해 현재 공까지 색이 다르고 사이즈가 작으면 총합에 크기를 더해 정답을 구했다.

for(int i=1; i<N; i++){
	for(int j=0; j<i; j++){
        if(v[j].size >= v[i].size)
        	break;
            
        if(v[j].color != v[i].color)
	    	ans[v[i].num] += v[i].size;
    }
}

 

2. 틀린 이유

공의 최대 개수가 200,000개로써

최악의 경우인 모든 공이 크기가 다를 때 1+2+...+199999로써 약 200억번 반복문이 수행되므로 시간초과가 난다. O(N*N)

 

3. 최종 풀이

변수를 좀 더 두어 반복을 줄여 O(N)으로 줄였다.

- 현재까지의 최대 크기 pivot

- 현재까지의 공 크기의 총합 cSize

- 현재까지의 pivot 미만의 공 크기의 총합 pSize

을 두어 반복마다 조건에 따라 해당 공을 가진 플레이어의 점수를 계산한다.

 

특히 색깔별 pivot, cSize, pSize를 가지고 있는 acc배열을 구현하여

반복에 따라 현재까지 공 크기의 총합 cSize에서 빼야할 색깔별 pSize를 갱신한 뒤 계산하는 것이 중요했다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Info{
	int num, color, size, ans;
};

struct State{
	int pivot, pSize, cSize;
};


bool comp1(Info a, Info  b){
	return a.size < b.size;
}

bool comp2(Info a, Info b){
	return a.num < b.num;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, c, s;

	cin >> N;
	vector<Info> v(N);
	vector<State> acc(N);
    
	for (int i = 0; i < N; i++){
		cin >> c >> s;
		v[i] = { i, c - 1, s, 0 };
	}

	// size 순으로 정렬
	sort(v.begin(), v.end(), comp1);

	// init with v[0]
	int pivot = v[0].size,
		pTot = 0,
		cTot = v[0].size;

	acc[v[0].color].cSize = v[0].size;
	acc[v[0].color].pivot = v[0].size;

	// start calculating at v[1]
	for (int i = 1; i < N; i++){
		int idx = v[i].color;

		// 색별로 pivot과 pivot 미만 크기들의 합, 현재까지의 총 합 갱신
		if (acc[idx].pivot < v[i].size){
			acc[idx].pivot = v[i].size;
			acc[idx].pSize = acc[idx].cSize;
		}

		if (pivot >= v[i].size){
			v[i].ans = pTot - acc[idx].pSize;
		}
		else{
			v[i].ans = cTot - acc[idx].cSize;

			pivot = v[i].size;
			pTot = cTot;
		}
		// 공통
		acc[idx].cSize += v[i].size;
		cTot += v[i].size;

	}

	// num 순으로 정렬
	sort(v.begin(), v.end(), comp2);

	for (int i = 0; i < N; i++)
		cout << v[i].ans << "\n";

	return 0;
}