[백준] 14658번. 하늘에서 별똥별이 빗발친다(JAVA)

문제

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

---

풀이(42분)

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

public class Main {
    static List<Star> stars = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int squareSize = Integer.parseInt(st.nextToken());
        int starCount = Integer.parseInt(st.nextToken());

        for (int i = 0; i < starCount; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            stars.add(new Star(x, y));
        }

        int maxStarsInSquare = 0;
        for (Star anchorA : stars) {
            for (Star anchorB : stars) {
                int starInside = countStarsInSquare(anchorA.x, anchorB.y, squareSize);
                maxStarsInSquare = Math.max(maxStarsInSquare, starInside);
            }
        }

        System.out.println(starCount - maxStarsInSquare);
    }

    private static int countStarsInSquare(int xStart, int yStart, int squareSize) {
        int count = 0;
        for (Star star : stars) {
            if (star.x >= xStart && star.x <= xStart + squareSize &&
                    star.y >= yStart && star.y <= yStart + squareSize) {
                count++;
            }
        }
        return count;
    }

    static class Star {
        int x;
        int y;

        public Star(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

---

문제 풀이 전략

 

✅ 문제 조건 정리

• 좌표 범위:
  n, m ≤ 500,000
  l ≤ 100,000
• 별의 개수 k: 100 이하

→ n과 m을 기준으로 탐색하는 완전탐색 접근은 시간 초과 발생 가능성이 매우 높음.

---

💡 핵심 아이디어

• k의 최댓값은 100이므로,
  이를 기준으로 O(k²) 수준의 탐색은 충분히 수행 가능하다.
• 한 별을 기준으로 트램펄린(정사각형)을 설치할 경우,
  해당 별이 모서리에 위치해야만 최적의 위치를 찾을 수 있음.
• 즉, 임의의 한 별을 정사각형의 좌상단 모서리 또는 우하단 모서리로 두고 탐색하는 전략.

---

✅ 구현 전략

1. 모든 별쌍 (별 A, 별 B)에 대해 순회하며 다음을 수행:
   • 별 A의 x좌표, 별 B의 y좌표를 좌상단 모서리 기준으로 설정
   • 해당 좌표를 기준으로 l x l 정사각형 내에 있는 별의 수를 탐색
2. 가장 많은 별을 포함하는 사각형을 찾고,
   K - 포함된 별의 수를 결과로 출력

---

⏱ 시간 복잡도

• O(k²) 쌍에 대해 각 사각형 내부를 O(k)로 확인 → O(k³)
• k ≤ 100이므로 최대 약 1,000,000회 연산, 시간 내 해결 가능