boj 10800 컬러볼

www.acmicpc.net/problem/10800

10800번: 컬러볼

 

어떤 공은 자신보다 색이 같거나 크기가 크거나 같은 공을 잡을 수 없습니다.

즉, 색이 다르고, 크기가 작은 공을 잡을 수 있습니다.

 

저는 공의 색에 대한 누적합(colorsum), 크기에 대한 누적합(sizesum), 전체 누적합(sum)을 모두 구하면서 답을 찾았습니다.

 

우선 공의 크기 -> 색 별로 오름차순 정렬합니다. (출력할 때 인덱스를 맞춰줘야하니 인덱스를 유지해줍니다.)

이제 크기가 작은 공부터 하나씩 꺼내 sum, colorsum, sizesum을 갱신합니다.

 

그럼 현재 공이 잡을 수 있는 공은

전체 합 - 같은 색의 크기 합 - 같은 크기의 크기 합 + 자신의 크기로 구해주시면 됩니다.

(같은 색과 같은 크기는 잡을 수 없으며 자신은 두 번 뺀 값이기때문에 자신의 크기를 더한 것입니다.)

 

하지만 이걸로 끝내기엔 예외가 하나 더 있습니다.

"자신과 색과 크기 모두 같은 공" 끼리는 답이 모두 같습니다.

저는 여기에서 예외처리가 안되어 pre배열에 이전 공의 정보를 유지하였습니다.

이전 공의 색과 크기가 모두 같으면 이전 ans값을 넣어줍니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int idx;
        int color;
        int size;
 
        public Pair(int idx, int color, int size) {
            this.idx = idx;
            this.color = color;
            this.size = size;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Pair> list;
    static int sum[] = new int[200001];
    static int colorsum[] = new int[200001];
    static int sizesum[] = new int[2001];
    static int ans[] = new int[200001];
    static int N;
 
    static void func() {
        int pre[] = new int[3];
        for (int i = 1; i <= N; i++) {
            int idx = list.get(i - 1).idx;
            int color = list.get(i - 1).color;
            int size = list.get(i - 1).size;
 
            sum[i] = sum[i - 1] + size;
            colorsum[color] += size;
            sizesum[size] += size;
 
            if (color == pre[1] && size == pre[2])
                ans[idx] = ans[pre[0]];
            else
                ans[idx] = sum[i] - colorsum[color] - sizesum[size] + size;
 
            pre[0] = idx;
            pre[1] = color;
            pre[2] = size;
        }
 
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i <= N; i++) {
            sb.append(ans[i]).append("\n");
        }
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        int x, y;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            list.add(new Pair(i, x, y));
        }
 
        Collections.sort(list, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                if (o1.size == o2.size)
                    return o1.color - o2.color;
                else
                    return o1.size - o2.size;
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}