[BOJ][Java] Q14658 - 하늘에서 별똥별이 빗발친다

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

문제 풀이

구역의 크기가 가로,세로 각 50만이고, 트램펄린 또한 한 변의 길이가 10만이나 된다. 

따라서 2차원배열에 별의 위치를 저장해놓고 탐색하는 방식은 사용할 수 없다.

별의 개수를 보면 최대 100개밖에 되지 않으므로, 별을 기준으로 반복문을 돌리며 찾아주면 된다.

 

또, 문제에 애매하게 써있어서 헷갈렸는데

(별똥별이 떨어지는 위치는 겹치지 않으며 별똥별은 트램펄린의 모서리에 부딪혀도 튕겨나간다!) 

이 부분에서 "모서리에 부딪힌다"는 게 의미하는 바는,

예를 들어 (0,0) 위치에 트램펄린을 배치한다고 했을 때, 왼쪽 그림이 아닌 오른쪽 그림처럼 배치된다는 뜻이다.

난 이것부터 문제가 이해가 안가서 엄청 삽질하다가 이차원배열이 아닌 좌표평면으로 생각하고 푸니까 이해가 갔다.ㅠㅠ

(0,0)부터 (2,2)까지의 사각형인 것!

 

이제 문제를 이해했으니, 트램펄린을 잘 배치하여 별의 개수를 세어 주기만 하면 된다.

나는 3중for문을 사용했다.

우선, 트램펄린 위치의 기준점이 될 별 now을 구한다.(1번 for문)

 

그리고 그 별을 포함하도록 트램펄린의 시작점을 지정해준다 (2번 for문)

이 때, now.x-L ~ now.x+L , now.y -L ~now.y+L 을 이중for문으로 전부 검사해줄 필요는 없고,

한 쪽 방향만 검사하면 된다. 다른 별을 기준으로 할 때 검사하는 경우의 수와 겹치기 때문이다.

예를 들어, 아래 그림에서 1번 별이 now이다. L은 2이다.

내가 now.x-L ~ now.x 방향만 트램펄린의 시작점으로 검사한다고 가정하자.

그럼 다음과 같이 세 경우만 검사한다.

1번 별이 위에 있는 2,3번 별과 겹치는 경우는 다음과 같이 2번별/3번별을 기준으로 했을 때의 트램펄린 위치에서 검사해줄 것이다.

따라서, 한쪽 방향으로만 검사해주면 된다.

 

트램펄린 위치를 정해주었으면, 이제 각각의 별을 돌며 그 트램펄린 범위에 포함되어있는지 검사한다.(3번 for문)

포함되는 별을 세어 주고, max값을 저장하며 나아간다.

 

마지막에 K-max를 출력해주면 끝이다.

---

package simulation;

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

public class Q14658_하늘에서별똥별이빗발친다 {
    /*[골드4]Q14658 - 하늘에서 별똥별이 빗발친다*/
    static int N, M, L, K;
    static Pos[] stars;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        stars = new Pos[K];

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

        int maxDefense=0;
        for(int p=0;p<K;p++){
            Pos now = stars[p]; //트램펄린 시작위치의 기준점이 되는 별
            //i: 트램펄린 시작위치 x좌표, j: 트램펄린 시작위치 y좌표
            for(int i=now.x-L;i<=now.x;i++){
                int j = now.y;
                if(i<0) continue;

                //전체 별을 돌며, 트램펄린에 포함되어있는지 확인
                int cnt=0;
                for(int q=0;q<K;q++){
                    Pos check = stars[q];
                    if(i<=check.x && check.x<=i+L && j<=check.y && check.y<=j+L)
                        cnt++;
                }
                maxDefense = Math.max(maxDefense,cnt);
            }
        }
        System.out.println(K-maxDefense);
    }

    static class Pos{
        int x,y;

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

​