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

문제 (Gold 4)

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

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

---

풀이

N과 M의 범위가 500,000까지이므로, 이를 모두 완전탐색하면 시간초과가 난다.

하지만, K의 개수는 100개 이하이기 때문에 K를 이용해서 탐색을 진행하면 된다.

 

위의 사진은 문제 예시를 좌표에 나타낸 것이다.

별들을 이중 for문으로 돌며, 각각에서 x좌표 y좌표를 추출하여 그 범위를 탐색한다.

빨간색 점은 각 번호에서 추출된 x, y좌표를 나타내고 이를 좌상단으로 하여 L*L만큼의 범위를 탐색하면 된다.

별들이 모서리에 존재하게 할 수록, 더 많은 별들을 포함할 수 있다는 관점이다.

위 예시의 경우에서는 5번 점의 x를 추출하고 2번점의 y를 추출한 빨간 점에서 트램펄린을 놓았을 때,

가장 많은 별을 포함하게 된다는 것을 알 수 있다!

코드

package bruteForce;

import java.util.*;
import java.io.*;

public class BOJ_14658_하늘에서별똥별이빗발친다 {
    static int N, M, L, K;
    static List<int[]> stars;
    public static void main(String[] args) throws Exception{
        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 ArrayList<>();
        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.add(new int[]{x, y});
        }
        int res = Integer.MIN_VALUE;
        for(int[] s1: stars){
            for(int[] s2: stars){
                res = Math.max(res, boundStar(s1[0], s2[1]));
            }
        }
        System.out.println(K-res);
    }

    private static int boundStar(int i, int j) {
        int res = 0;
        for(int[] s:stars){
            if(i<=s[0]&&s[0]<=i+L && j<=s[1]&&s[1]<=j+L ) res++;
        }
        return res;
    }
}

제출

500,000*500,000을 완탐하려 해서 실패! ( 안되는건 알지만 혹시나~해서 트라이! )