[백준 / 골드3] 14658 하늘에서 별똥별이 빗발친다 (Java)

문제 보기

사용한 것

• 모든 경우의 수를 탐색하는 브루트포스

풀이 방법

(1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100)

• 문제의 조건은 위와 같다.
• 따라서 트램폴린을 놓는 경우의 수를 n, m으로 반복문 돌린다면, 최악의 경우 500,000 x 500,000 x 100을 탐색해야한다. (트램폴린 놓는 경우의 수 x 별 하나씩 계산)
• 따라서 다른 방법으로 접근해야한다.

• 트램폴린은 효율적으로 사용하려면, 특정 별똥별이 트램폴린의 가장자리인 경우부터 시작하면 된다.
• 트램폴린은 x, y좌표를 가지므로 별똥별 2개를 선택하여 각각 트램폴린의 x좌표, y좌표로 시작한다면 별똥별 2개는 모서리에 포함된다.
• 따라서 별똥별 2개를 선택하여 반복문을 진행한다면 k로 반복문을 돌려 100 x 100 x 100으로 탐색할 수 있다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int l = Integer.parseInt(line[2]);
        int k = Integer.parseInt(line[3]);

        int[][] stars = new int[k][2];
        for (int i = 0; i < k; i++) {
            line = br.readLine().split(" ");
            stars[i] = new int[]{Integer.parseInt(line[0]), Integer.parseInt(line[1])};
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                int ct = 0;
                int tx = stars[i][0];
                int ty = stars[j][1];

                for (int[] star : stars) {
                    if (!isBound(tx, ty, star[0], star[1], l)) {
                        ct++;
                    }
                }

                answer = Math.min(ct, answer);
            }
        }

        System.out.println(answer);
    }

    public static boolean isBound(int tx, int ty, int sx, int sy, int l) {
        return sx >= tx && sx <= tx + l && sy >= ty && sy <= ty + l;
    }
}