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

14 Oct 2023 in Algorithm on 브루트포스 알고리즘

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

풀이

N, M의 범위가 500000이기 때문에 이것을 기준으로 탐색을하면 시간초과가 난다.

K가 100까지인것을 보고 K를 기준으로 탐색했다.

트램펄린의 어느 모서리에 별이 위치해있어야 많은 별을 담을 수 있다.

별 두개를 선택해 별a의 x좌표와, 별b의 y좌표를 한쪽 꼭지점으로 하는 길이 L의 사각형을 만들어 거기에 별이 얼마나 들어가는지 체크했다.

---

메모리: 14712KB

시간: 160ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int x;
        int y;

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

    static ArrayList<Node> list;

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

        list = 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());
            list.add(new Node(x, y));
        }

        int res = 0;
        for (Node a : list) {
            for (Node b : list) {
                res = Math.max(res, inBound(a.x, b.y, L));
            }
        }

        System.out.println(K - res);
    }

    private static int inBound(int i, int j, int l) {
        int cnt = 0;
        for (Node s : list) {
            if (s.x >= i && s.x <= i + l && s.y >= j && s.y <= j + l) {
                cnt++;
            }
        }

        return cnt;
    }

}