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

문제 설명 :

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

 

문제 요약 :

1. 주어진 좌표에서 여러 개의 별똥별이 떨어진다
2. l * l 크기의 트램펄린을 설치하여 별똥별을 막을 수 있다.
3. 지면에 부딪치는 별똥별의 최소 개수 구하기

 

문제 풀이 시간 : 1시간

문제 성공 여부 : 실패

 

 

접근 방법(실패) :

1. 떨어지는 별똥별의 위치에 집중

먼저, 문제를 보면 확실하게 알 수 있는 사실이 있다.

바로 엄청나게 큰 N,M의 크기와 l의 크기이다.

 

코테에 익숙하지 않은 사람도 N*M과 L*L로는 절대 접근하면 안 된다는 것을 알 수 있을 것이다.

 

그럼 관건은 최대 100개라는 아주 귀여운 K의 개수에 집중을 해야 한다.

 

각각의 별똥별이 떨어지는 위치에 집중을 해야한다.

 

 

 

 

근데 어떻게 함..?

 

바로 이 부분에서 1시간의 시간을 소비해 버렸다.

 

비록 추후 다른 사람들의 풀이를 보고 풀었지만 나의 접근 방법은 다음과 같았다.

 

 

각 별똥별의 위치를 기준으로 트램펄린의 위치 구하기

K*K는 시간복잡도에 아무 지장이 없기 때문에, 각각의 별똥별 위치에서 트램펄린을 두는 방법을 생각했다.

 

하나의 별똥별을 기준으로 좌상단, 우상단, 좌하단, 좌상단에 트램펄린을 두고,

나머지 99개의 별똥별들이 내부에 있는지 파악하면 될 것 같았다.

이렇게 별똥별을 기준으로 4 사분면의 트램펄린을 놓으면 간단하게 해결이 될 줄 알았다.

 

하지만..

 

반례

다음과 같이 별똥별이 떨어진다면 어떻게 될까?

 

각 점에서 트램플린을 어떻게 놓아도 모든 별똥별을 커버할 수 없다!

 

이렇게 별똥별의 위치에서 시작할 수 없는 경우들이 존재하게 된다.

 

 

시도한 다른 방법

각 점에서 시작하는 방법으로는 불가능하기 때문에, 특정 별똥별 점의 중앙에 트램펄린을 놓는 방법을 생각해 보았다.

 

바로 이렇게 각각의 점들의 x, y 좌표의 중앙값을 계산하여 점을 그린 후, 해당 점을 중앙으로 가지는 트램펄린을 설치하는 것이다!

 

 

안 되는 이유

간단하게 생각해 봤을 때,

x에서 나올 수 있는 모든 중앙값 개수 * y에서 나올 수 있는 모든 중앙값 개수를 구해야 한다.

 

x에서 나올 수 있는 모든 중앙값 개수의 최댓값은 다음과 같다.

== 1~100의 전체 부분집합

== 2^100

== 시간초과

 

접근 방법(성공) :

1. 두 개의 점의 각각의 x와 y값으로 모서리의 좌표를 구한다.
2. 모서리의 좌표를 기준으로 트램펄린을 배치한다.

 

이렇게, 두 점의 좌상단 점을 구하고,

해당 위치에 트램펄린을 우하단에 두게 되면 최소 1개를 포함하는 가장 효율적인 트램펄린 설치가 가능해진다!

전체 코드(성공) :

public class Main {
    static class Star {
        int x, y;

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

    static Star[] stars; // 별똥별 좌표

    public static void main(String[] args) throws IOException {
        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());

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

        int max = 0;
        for(int i=0; i<K; i++){
            for(int j=0; j<K; j++){
                int x = stars[i].x;
                int y = stars[j].y;

                max = Math.max(max, getStars(x, y, L)); // 가장 많이 막을 수 있는 개수
            }
        }

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

    static int getStars(int x1, int y1, int L) {
        int cnt = 0;
        for(Star star : stars){
            int x = star.x;
            int y = star.y;
            // (x1,y1)과 (x1+L, y1+L)의 내부에 위치하는지
            if(x >= x1 && y >= y1 && x <= x1 + L && y <= y1 + L){ 
                cnt++;
            }
        }
        return cnt;
    }
}