백준 컬러볼(10800)

컬러볼

1. 힌트

1) 작은 공부터 계산하면 어떤 공을 계산할 때, 이전에 넣은 공들은 모두 자기 자신보다 크기가 작거나 같으므로 편하게 구현할 수 있습니다.

2) (지금까지 계산한 공들의 크기 $-$ 지금 계산하는 공과 색깔이 같은 공들의 크기의 합)을 계산하면 $i$번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 계산할 수 있습니다.

3) 하지만 서로 같은 크기의 공이 존재해서 문제입니다. 다행히도 크기의 범위가 $1 \le S_i \le 2000$

2. 접근

1) 순서를 강제할 수 있을까?

순서가 상관없는 어떤 연산이 있을 때, 우리가 임의로 연산의 순서를 정하면 구현이 간단해지는 경우가 있습니다.
이 문제에서는 가장 작은 공부터 차례대로 계산하고, 지금까지 계산한 공들의 크기의 합 $p$를 유지하면 지금 계산하려는 공보다 작은 공들의 크기의 합을 알 수 있습니다. 물론, 크기가 같은 공들도 있으니 이를 처리해줘야겠죠. 여기에서 크기가 같은 경우도 제외해주려면 색깔 별로 크기들의 합을 저장하는 배열 $C$도 유지해줍시다. 이러면 매 번 넣을때 마다 $O(N)$의 검색을 수행할 필요가 없습니다.

문제를 보니 $S_i$

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		// S[x] = x크기인 컬러볼들 (번호, 색)
		ArrayList<ArrayList<Pair>> S = new ArrayList<>(2001);
		for (int i = 0; i <= 2000; i++) S.add(new ArrayList<>());
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			S.get(s).add(new Pair(i, c));
		}
		int p = 0; // 지금까지 계산한 공들의 크기의 합
		int[] C = new int[N + 1]; // 색깔별 크기들의 합 저장
		int[] ret = new int[N + 1]; // i번째 공이 집을수 있는 공의 크기 합 저장
		for (int i = 1; i <= 2000; i++) {
			for (Pair x : S.get(i)) ret[x.num] = p - C[x.color];
			p += S.get(i).size() * i;
			for (Pair x : S.get(i)) C[x.color] += i;
		}
		for (int i = 1; i <= N; i++) bw.append(ret[i]).append("\n");
		System.out.print(bw);
	}

}
class Pair {
	int num, color;
	
	Pair (int n, int c) { num = n; color = c; }
}

1) 시간 복잡도

$O(N)$입니다. 중간에 2중 for문이 보이지만, 어차피 같은 원소를 두 번 이상 계산하지 않으므로 전체 시간 복잡도는 공의 개수와 같습니다.