BOJ 10800 컬러볼 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 고등부 2번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 4번)

3개의 풀이가 나왔다.

1. 시간초과

하나씩 다 더해줌

2. 런타임

2차원 배열을 만들어서 무게별로 나누고 또 거기에서 컬러별로 나눴음

2000 * 2e5 * 4 = 1G가 넘어가서 런타임 에러

3. 정답

블로그를 조금 참고했지만, 짜고나니 거의 똑같게 나옴...

total 스코어 idea를 참고함.

	import java.util.*;
	import java.io.*;
	/**
	* BOJ 10800 컬러볼 풀이
	* https://gist.github.com/KSH-code/e705293348cbd1aea4567002e516a388
	*/
	class Ball implements Comparable<Ball>{
	public int color, weight, idx;
	public Ball(int color, int weight, int idx){
	this.color = color;
	this.weight = weight;
	this.idx = idx;
	}
	@Override
	public int compareTo(Ball arg){
	return this.weight - arg.weight;
	}
	}
	class Main {
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	int N = Integer.parseInt(br.readLine());
	int score[] = new int[N];
	int color[] = new int[N+1];
	int total = 0;
	Ball temp[] = new Ball[N];
	for(int i = 0; i<N; i++){
	String str1[] = br.readLine().split(" ");
	int c = Integer.parseInt(str1[0]);
	int w = Integer.parseInt(str1[1]);
	temp[i] = new Ball(c, w, i);
	}
	Arrays.sort(temp);
	for(int i = 0, j = 0; i<N; i++){
	for(; temp[j].weight<temp[i].weight; j++){
	total += temp[j].weight;
	color[temp[j].color] += temp[j].weight;
	}
	score[temp[i].idx] += total - color[temp[i].color];
	}
	for(int i = 0; i<N; i++){
	bw.write(score[i] + "\n");
	}
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub