[백준 10800번] 컬러볼

문제 링크: 10800번 컬러볼

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

 

공을 먼저 크기에 따른 순서대로 정렬한다.

다음과 같은 예시가 있다고 생각해보자.

 

정렬후 인덱스 idx	0	1	2	3	4	5	6	7	8
size	2	3	4	10	11	12	15	16	17
color	3	2	1	2	2	1	2	3	1
sum	0	2	5	9	19	30	42	57	73
csum[1]	0	0	0	4	4
csum[2]	0	0	3	3	13
csum[3]	0	2	2	2	2

 

예를 들어, size가 11인 공의 경우

1. size를 고려한다면, 자신보다 앞에 있는 모든 공을 먹을 수 있다. -> sum[4] = 19

2. color를 고려한다면, 자신보다 앞에 있는 모든 공 중 동일한 color의 공은 먹을 수 없다. -> csum[2] = 13

곧 6을 먹을 수 있다.

즉 current = balls[idx]라 하면

SUM_OF_SIZE_OF_CATCHABLE_BALLS[current] = sum[idx] - csum[idx.color];

 

그러나 다음과 같이, 동일한 size의 공이 여러개 있다면 문제가 달라진다.

 

정렬후 인덱스 idx	0	1	2	3	4	5	6	7	8
size	1	2	4	4	4	4	4	5	6
color	1	2	1	3	2	2
sum	0	1	3	7	11	15
csum[1]	0	1	1	5	5	5
csum[2]	0	0	2	2	2	6
csum[3]	0	0	0	0	4	4

 

여기서 idx=4인 공이 사로잡을 수 있는 공의 크기의 합은 얼마일까?

직접 계산해보면 1이지만, 앞선 식을 이용하면 11-2 = 9라는 답이 나온다.

이는 size=4인 공들(idx=2, 3인 공들)은 먹을 수 없지만 앞서있다는 이유만으로 먹을 수 있다고 계산되었기에 나타난 문제이다.

 

이를 위해 별도의 인덱스를 하나 추가로 설정해서,

같은 size의 공들에 대해서는 정답을 먼저 계산해서(idx=2인 공을 만나는 순간, 이 때 sum과 csum이 size=4인 모든 공에 대해 적용되어야 하는 값이다) answer에 저장한 후,

다시 앞으로 돌아와서(아래 코드에서는 t를 이용) csum과 sum을 갱신하고,

그 후 size=5(idx=7)인 공으로 넘어가는 방법을 택할 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

class Ball {
    int size;
    int color;
    int id;

    Ball(int size, int color, int id) {
        this.size = size;
        this.color = color;
        this.id = id;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        /* input begins */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

        Ball[] balls = new Ball[n];
        int sum = 0;
        int[] csum = new int[n+1];
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int color = Integer.parseInt(st.nextToken());
            int size = Integer.parseInt(st.nextToken());
            balls[i] = new Ball(size, color, i);
        }
        /* input ends */

        // 크기 순으로 정렬
        Arrays.sort(balls, Comparator.comparingInt(o -> o.size));

        for (int i = 0; i < n; i++) {
            Ball cur = balls[i];
            Ball next = i < n-1 ? balls[i+1] : null;

            int walker = i + 1;

            if (i < n-1 && cur.size == next.size) {
                answer[cur.id] = sum - csum[cur.color];

                // 별도의 인덱스 walker를 통해 answer을 먼저 채운 후에
                while (balls[walker].size == balls[walker-1].size) {
                    answer[balls[walker].id] = sum - csum[balls[walker].color];
                    walker++;
                    if (walker >= n) break;
                }

                // sum과 csum을 갱신해준다.
                for (int t = i; t < walker; t++) {
                    sum += balls[t].size;
                    csum[balls[t].color] += balls[t].size;
                }

                i = walker - 1;
            } else {
                answer[cur.id] = sum - csum[cur.color];
                csum[cur.color] += cur.size;
                sum += cur.size;
            }
        }

        /* output begins */
        StringBuilder sb = new StringBuilder();
        for (int item : answer)
            sb.append(item).append('\n');
        System.out.println(sb);
        /* output ends */
    }
}