[백준] 14658 하늘에서 별똥별이 빗발친다

문제링크 : https://www.acmicpc.net/problem/14658

14658번: 하늘에서 별똥별이 빗발친다

package study.mar_3week;

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

public class BJ14658 {
    static int n, m , l, k, max;
    static class Node{
        int y; int x;
        Node(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        ArrayList<Node> star = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            star.add(new Node(y, x));
        }
        for (Node n1 : star){
            for (Node n2 : star){
                int cnt = 0;
                for (Node node : star){
                    if (n1.x <= node.x && node.x <= n1.x+l && n2.y<=node.y&& node.y<=n2.y+l){
                        cnt ++;
                    }
                }
                max = Math.max(max, cnt);
            }
        }

        System.out.println(k-max);
    }
}

해설 : n, m의 범위가 넓기 때문에 완전탐색으로 풀이할 시 시간초과가 발생한다. 따라서 별의 위치를 기준으로 탐색해야 한다.

별의 좌표를 모두 저장한 후, 한 점을 기준으로 다른 별들의 위치가 트램펄린의 길이 안에 있는지를 확인하여 카운트 해주면 된다.