백준 14658번 <하늘에서 별똥별이 빗발친다>

백준 알고리즘 14658번

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

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

---

14658번

별똥별이 떨어진다!

지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 L*L 크기의 트램펄린을 준비했다. 별똥별이 어디로 떨어질지는 이미 알고 있기 때문에, 욱제는 이 트램펄린으로 최대한 많은 별똥별을 우주로 튕겨낼 계획이다. 최대한 많은 별똥별을 튕겨내도록 트램펄린을 배치했을 때, 지구에는 몇 개의 별똥별이 부딪히게 될까? (별똥별이 떨어지는 위치는 겹치지 않으며 별똥별은 트램펄린의 모서리에 부딪혀도 튕겨나간다!) 트램펄린은 비스듬하게 배치 할 수 없다.

 

입력으로 첫 줄에 별똥별이 떨어지는 구역의 가로길이 N, 세로 길이 M, 트램펄린의 한 변의 길이 L, 별똥별의 개수 K가 들어온다. 

그 다음 K개의 줄에 걸쳐 별똥별이 떨어지는 지점이 (가로, 세로) 좌표로 들어온다.

 

출력으로 트램펄린을 잘 설치했을 때, 지표면에 떨어지는 별똥별의 최소 수를 구하여라.

---

문제 해결

처음에 생각한 방법은 (0, 0) 부터 트램펄린을 설치해보자! 였는데 그러면 50만 * 50만 만큼 트램펄린을 설치해봐야 하기 때문에 엄청 오래 걸린다.

 

그래서 (0, 0) 부터 시작하지 말고 별똥별이 떨어지는 위치를 기준으로 생각하면 되지 않을까라고 생각했다.

그래서 별똥별이 떨어지는 가로 위치를 저장한 J와 세로 위치를 저장한 I 리스트를 만들었다.

 

별똥별의 개수가 최대 100개이고 이 100개가 모두 가로/세로의 위치가 다 다른 경우에 I와 J 의 크기는 최대 100이다.

결국 이 I와 J를 조합해서 나오는 좌표를 기준으로 트램펄린을 설치하면 되는데 이때 최대 100 * 100 만큼 설치해보면 된다. 그리고 트램펄린을 설치한 후에 별똥별이 트램펄린에 떨어지는지 확인하는 것은 별똥별의 개수만큼 for문을 돌면서 범위 안에 들어오는지 확인하면 된다.

따라서 이 방법은 log(100 * 100 * 100) = log (100만) 충분히 가능하다고 판단했다.

 

이 방법을 사용하기 전에 고려했던 것은 별똥별의 위치들로 이루어지지 않은 좌표에 트램펄린을 설치했을 때 제일 많이 튕길 수 있는 경우가 있지 않을까 였는데 그런 경우는 별똥별을 포함하고 있는 큰 사각형인 경우 밖에 없다고 생각했다.

그리고 이 경우는 아래와 같이 트램펄린을 설치하는 것과 똑같다.

결국 큰 사각형 안에 별똥별이 있는 경우는 별똥별이 트램펄린의 끝에 있도록 바꿔서 포함할 수 있기 때문에 해당 풀이가 문제가 없다고 판단했다.

 

그리고 이 문제는 가로가 N 세로가 M으로 주어졌는데 나는 세로가 N 가로가 M이 편해서 코드 상에서는 바꿔서 풀이를 진행했다. 그리고 위의 그림에서 보이는 것처럼 별똥별의 위치가 모서리(?)에 주어지기 때문에 만약 (0, 0)에 3크기의 트램펄린을 설치한다고 하면 별똥별의 가로와 세로가 0부터 3 사이인지 확인하면 된다. 모서리에 주어지기 때문에 3이 포함되어야 한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

public class BOJ_14658 {
    static class Point {
        int i, j;

        public Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    static Point[] star;
    static int N, M, L, K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        M = Integer.parseInt(inArr[0]);     // M : 구역의 가로 길이
        N = Integer.parseInt(inArr[1]);     // N : 구역의 세로 길이
        L = Integer.parseInt(inArr[2]);     // L : 트램펄린 길이
        K = Integer.parseInt(inArr[3]);     // K : 별똥별의 개수

        star = new Point[K];            // star[k] : k번 별똥별이 떨어지는 위치
        HashSet<Integer> tempI = new HashSet<>();   // tempI : 별똥별이 떨어지는 위치들의 세로 좌표
        HashSet<Integer> tempJ = new HashSet<>();   // tempJ : 별똥별이 떨어지는 위치들의 가로 좌표
        for (int i = 0; i < K; i++) {
            // 가로위치, 세로위치 순으로 들어옴
            inArr = br.readLine().split(" ");
            star[i] = new Point(Integer.parseInt(inArr[1]), Integer.parseInt(inArr[0]));
            tempI.add(star[i].i);
            tempJ.add(star[i].j);
        }
        // end input
        ArrayList<Integer> I = set2list(tempI);
        ArrayList<Integer> J = set2list(tempJ);

        int count = 0;
        //  I랑 J의 최대 길이는 100
        // 별똥별의 개수가 최대 100개이고 이 별똥별의 세로나 가로가 다 다르다고 했을 떄
        // process에서 도는 for문의 최대는 100
        // log(100 * 100 * 100) = log(100만)
        for (int i = 0; i < I.size(); i++) {
            for (int j = 0; j < J.size(); j++) {
                count = Math.max(count, process(I.get(i), J.get(j)));
            }
        }
        System.out.println(K - count);
    }

    static int process(int si, int sj) {
        // (ei, ej) : 트램펄린의 오른쪽 아래 끝 위치
        int ei = Math.min(N, si + L);
        int ej = Math.min(M, sj + L);
        int cnt = 0;        // cnt : 트램펄린 안에 들어가는 별똥별의 개수

        // 별똥별의 개수는 최대 100
        // 별똥별을 보면서 트램펄린 안에 들어가는지 확인
        for (int k = 0; k < K; k++) {
            if (si <= star[k].i && star[k].i <= ei && sj <= star[k].j && star[k].j <= ej) {
                cnt++;
            }
        }
//        System.out.printf("------- (%d %d) -> (%d %d) --------- cnt = %d \n", si, sj, ei, ej,  cnt);
        return cnt;
    }

    static ArrayList<Integer> set2list(HashSet<Integer> set) {
        ArrayList<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        return list;
    }
}

---

결과

---

계속 1%에서 틀려서 왜 틀리지,,, 했는데 알고보니까 트램펄린을 설치하는 좌표를 설정할 때 list에서 i번째를 가져와서 사용해야 하는데 안가져오고 그냥 i를 쓰고 있었다,,, 

 

나 울어,,,

 

8 8 3 11
6 0
4 1
2 2
5 2
7 2
0 4
4 4
6 4
3 5
6 6
3 7

6
-------------
8 8 4 11
6 0
4 1
2 2
5 2
7 2
0 4
4 4
6 4
3 5
6 6
3 7

5
-------------
8 8 5 11
6 0
4 1
2 2
5 2
7 2
0 4
4 4
6 4
3 5
6 6
3 7

3
-------------
3 3 5 4
0 1
1 2
2 2
3 1

0
-------------
1 1 1 3
0 0
0 1
1 0

0
-------------
4 4 2 4
2 1
3 2
1 2
2 3

0