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

Problem 💻

단순한 브루트포스 문제지만 어떻게 풀어야할지 좀 고민해봐야 하는 문제이다.

---

 

Approach 1 ❌

• 좌표 완전 탐색
• 별 기준으로 완전 탐색

처음 풀이는 2가지였다. 좌표 완전 탐색과 별 기준 완전 탐색.

 

좌표 완전 탐색은 (1, 1)부터 (M-L, N-L)까지 x ~ x+L, y ~ y+L 사이의 겹치는 좌표가 있는지 하나하나씩 찾아서 최고값을 갱신해주는 방법이다. 하지만, 문제의 조건에 N, M은 최대 500,000으로 되어있기 때문에 이렇게 할 경우 L = 1인 최악의 경우 500,000 * 500,000으로 2500억 가까이 되는 연산이 일어난다. 당연히 시간초과이다.

 

그래서 생각한 방법이 별 기준으로 완전 탐색이다. 처음엔 별 좌표 기준으로 x ~ x+L, y ~ y+L 까지 겹치는 별들 중 최대값으로 구했다. 하지만, 제1, 2, 3, 4 사분면으로 나누어 구하는 것이 반례에 걸리지 않을 것 같다고 생각해서 각 별의 좌표를 중심으로 한 제 1, 2, 3, 4 사분면을 구해 최대값을 찾도록 하였다. 근데 이 방법은 반례가 있다.

 

. * .
* . *
. * .

 

위와 같은 별 위치가 주어지고 L이 3이라면 (1, 1)에 트램펄린을 두는 것이 모든 별을 다 튕겨낼 수 있다. 하지만, 방금 로직으로는 최대 3개까지의 별만 튕겨낼 수 있으므로 정답이 될 수 없다.

---

 

Approach 2 ⭕

• 주어진 별 좌표들의 모든 y 좌표 탐색

별똥별 두 개를 선택해서 하나는 x 좌표, 하나는 y 좌표만 가져온다. 왜 이렇게 푸냐면 최대한 별똥별들이 많이 모여있는 위치에 트램펄린을 배치해야 하기 때문이다.

 

. * .
* . *
. * .

 

위와 같은 상황일 때 (1, 2)의 x와 (2, 1)의 y를 가져오면 (1, 1)에 트램펄린을 설치할 수 있게된다. 그렇게해야 최대한 많은 별똥별을 튕겨낼 수 있다. 즉, 최대한 별들을 트램펄린 모서리에 위치시켜 많은 별똥별을 튕겨내는 것이다. 이를 그림으로 나타내면 다음과 같다.

 

---

 

Solution 💡

public class BOJ_14658 {
    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());

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

        int ret = 0;
        for (int s1 = 0; s1 < k; s1++) {
            int x = stars[s1][0];
            for (int s2 = 0; s2 < k; s2++) {
                int y = stars[s2][1];
                int cnt = 0;
                for (int s = 0; s < k; s++) {
                    if (x <= stars[s][0] && (x + l) >= stars[s][0] && y <= stars[s][1] && (y + l) >= stars[s][1]) cnt++;
                }

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

        System.out.println(k - ret);
    }
}

---

 

Reference 📄

https://www.acmicpc.net/board/view/146794

https://www.acmicpc.net/board/view/107552