백준 10800번: 컬러볼 (Java)

🎯 문제 목표

• 각 공은 색과 크기를 가진다.
• 모든 공 쌍에 대해 서로 다른 색이면서 작은 공의 크기만큼 점수를 획득한다.
• 각 공이 얻을 수 있는 총 점수를 출력한다.

---

✅ 풀이 전략 요약

1. Ball 객체 정의
   → color, size, index를 저장하는 클래스 생성

2. 정렬 기반 누적합 알고리즘
   → 공을 크기 기준으로 정렬하고, 같은 크기까지는 점수 계산을 미뤄둔다
   → 누적합을 활용해 총합과 색상별 합을 미리 관리한다

3. 투 포인터
   → 현재 공보다 작은 공들을 전부 포함시키는 방식으로 점수 누적

4. 색이 같은 경우 제외
   → 같은 색의 합은 제외하여 점수 계산

---

💡 핵심 개념

변수	의미
total	지금까지 본 공 중 크기가 현재 공보다 작은 공들의 전체 크기 합
colorSum[color]	특정 색상 공의 누적 크기 합
result[i]	i번 공이 얻을 수 있는 점수 (조건 만족하는 다른 공들의 크기 합)

---

💻 전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static class Ball implements Comparable<Ball> {
        int color, size, index;
        Ball(int color, int size, int index) {
            this.color = color;
            this.size = size;
            this.index = index;
        }

        @Override
        public int compareTo(Ball o) {
            return this.size - o.size;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Ball[] balls = new Ball[n];
        int maxColor = 0;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            balls[i] = new Ball(c, s, i);
            maxColor = Math.max(maxColor, c);
        }

        Arrays.sort(balls);  // 크기 기준 정렬

        int[] result = new int[n];
        int[] colorSum = new int[maxColor + 1];
        int total = 0, j = 0;

        for (int i = 0; i < n; i++) {
            Ball cur = balls[i];

            // 현재 공보다 작은 크기 공들의 누적합 업데이트
            while (balls[j].size < cur.size) {
                total += balls[j].size;
                colorSum[balls[j].color] += balls[j].size;
                j++;
            }

            // 총합 - 같은 색상 누적합
            result[cur.index] = total - colorSum[cur.color];
        }

        for (int r : result) System.out.print(r + "\n");
    }
}

---

📌 정리

• 정렬 후 투 포인터 방식으로 누적합을 갱신하면서 탐색
• 같은 색은 점수에 포함하지 않도록 색상별 합을 따로 관리
• 복잡한 브루트포스보다 훨씬 효율적인 누적합 전략