백준 14658번 하늘에서 별똥별이 빗발친다(자바) #

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

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

1437

441

358

31.598%

문제

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

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

“에이, 거짓말!”

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

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

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

지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 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)

출력

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

예제 입력 1 복사

12 10 4 7
2 4
7 3
3 1
5 6
4 7
12 10
8 6

예제 출력 1 복사

3

---

트램펄린을 한칸씩 옮기며 모든 경우를 탐색하는 방법 -  N,M이 500000까지 가능하기 때문에 시간 초과가 나오기 때문에 이 방법은 불가능

 

두 점을 트램펄린의 모서리에 있게 하는 모든 경우에 대해 별똥별의 개수를 세고 가장 작은 값을 출력하면 된다.

import java.util.Scanner;

public class Main {
    static int n,m,l,k;
    static int[][] star;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        l = sc.nextInt();
        k = sc.nextInt();
        int cnt;
        int answer = 0;
        star = new int[k][2];
        for (int i = 0; i < k; i++) {
            star[i][0] = sc.nextInt();
            star[i][1] = sc.nextInt();
        }
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                int x = star[i][0];
                int y = star[j][1];
                cnt = 0;
                for (int[] dot : star) {
                    if (x <= dot[0] && x + l >= dot[0] && y <= dot[1] && y + l >= dot[1])
                        cnt++;
                }
                answer = Math.max(answer, cnt);

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

참고

백준 14658번 하늘에서 별똥별이 빗발친다 (C++) (tistory.com)

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

[BOJ] 14658번: 하늘에서 별똥별이 빗발친다 (Java) (velog.io)

[BOJ] 14658번: 하늘에서 별똥별이 빗발친다 (Java)