백준 14658 하늘에서 별똥별이 빗발친다 (Java)

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

1. 문제

“오빠! 나 얼마만큼 사랑해?”

“널 위해서라면 저기 저 하늘의 별이라도 따다 줄 수 있어. 지금 따줄까?”

“에이, 거짓말!”

“정말이야. 한 번 봐봐!”

욱제는 하늘을 발로 차버렸다. 그랬더니 정말 별이 떨어졌다. 그런데, 정말로 별이 지구로 떨어지기 시작했다. 욱제는 지구를 지키는 정의의 용사가 되기로 결심했다.

“자기야, 나 세계를 지키고 올게. 꼭 돌아올 테니 조금만 기다려줘.”

지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 L*L 크기의 트램펄린을 준비했다. 별똥별이 어디로 떨어질지는 이미 알고 있기 때문에, 욱제는 이 트램펄린으로 최대한 많은 별똥별을 우주로 튕겨낼 계획이다. 하지만 학교 예산으로 트램펄린을 구매하는 욱제는 이 긴급한 와중에도 예산 심의 통과를 기다리느라 바쁘다!

욱제를 도와 세계를 구하자. 최대한 많은 별똥별을 튕겨내도록 트램펄린을 배치했을 때, 지구에는 몇 개의 별똥별이 부딪히게 될까? (별똥별이 떨어지는 위치는 겹치지 않으며 별똥별은 트램펄린의 모서리에 부딪혀도 튕겨나간다!) 트램펄린은 비스듬하게 배치 할 수 없다.

입력

첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 뜻한다. 이후 K개의 줄에 걸쳐 별똥별이 떨어지는 위치의 좌표 (x, y)가 주어진다. (0 ≤ x ≤ N, 0 ≤ y ≤ M)

출력

욱제가 트램펄린으로 최대한 많은 별똥별을 튕겨낼 때, 지구에 부딪히는 별똥별의 개수를 출력한다.

2. 풀이

지구의 가로 세로가 각각 50만이므로 모든 경우를 탐색하면 시간 초과가 난다. 따라서 다른 방법으로 풀어야 한다.

우선 최대한 많은 별똥별이 트램펄린 내에 들어가야 하므로 최소 하나의 별똥별은 트램펄린의 모서리에 들어가 있어야 한다.

하지만 하나의 별똥별을 기준으로 고려할 경우 위와 같은 상황이면

이런 식으로 한 쪽 방향에 있는 별만 계산하게 되어 정답을 구할 수 없게 된다.

이렇게 모든 별이 모서리에 있는 경우에 해를 구할 수 있다. 이를 계산하기 위해 별 두개를 잡아 한쪽 별에서 y, 다른 쪽 별에서 x를 가져와 해당 좌표를 좌상단에 놓는 트램펄린을 만들게 되면 해당 별들은 트램펄린의 모서리에 걸치게 되고, 위의 케이스도 해결할 수 있게 된다.

        for (int i = 0; i < stars.size(); i++) {
            for (int j = 0; j < stars.size(); j++) {

                int cnt = 0;
                for (Node star : stars) {
                    if (star.y >= stars.get(i).y && star.y <= stars.get(i).y + l && star.x >= stars.get(j).x && star.x <= stars.get(j).x + l) {
                        cnt++;
                    }
                }

                ans = Math.max(ans, cnt);
            }
        }

        System.out.println(k - ans);

각 별들에 대해 좌표를 하나씩 가져와 트램펄린의 꼭짓점으로 잡고, 해당 트램펄린의 위치에 대해 모든 별들 중 트램펄린에 들어가는 별의 개수를 구하여 최댓값을 갱신한다. 총 k개의 별에 트램펄린에 막히는 별의 개수가 ans이므로 둘의 차이를 출력하면 정답을 구할 수 있다.

 

3. 코드 전문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {


    static List<Node> stars;

    static int ans = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());
        int l = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());

        stars = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            tokenizer = new StringTokenizer(reader.readLine());

            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());


            stars.add(new Node(a, b));

        }



        for (int i = 0; i < stars.size(); i++) {
            for (int j = 0; j < stars.size(); j++) {

                int cnt = 0;
                for (Node star : stars) {
                    if (star.y >= stars.get(i).y && star.y <= stars.get(i).y + l && star.x >= stars.get(j).x && star.x <= stars.get(j).x + l) {
                        cnt++;
                    }
                }

                ans = Math.max(ans, cnt);
            }
        }

        System.out.println(k - ans);




    }
}

class Node{
    int y;
    int x;

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