[BOJ] 백준 14658. 하늘에서 별똥별이 빗발친다

문제

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

 

 

---

풀이

N과 M의 범위가 500,000이고, 시간 제한은 2초기 때문에 주의해야한다.

 

별똥별 수인 K는 100개이기 때문에, K를 이용해 문제를 해결하면 시간 초과를 피할 수 있다.

 

K를 이중 for문에서 순회하면서, 별똥별의 위치로 x, y 조합을 만든다.

그림에서 노란 점이 별똥별이라면 만들 수 있는 조합은 회색 점과 같다. 즉 탐색을 시작할 후보군 정도로 생각할 수 있다.

 

회색 점에서 화살표 방향인 우 하단 방향으로 L만큼 측정하며, 범위에 해당하는 star를 카운트하고 가장 최대 값을 구하면 된다.

 

 

 

여기서, 후보군이 아니라 별똥별의 위치에서 탐색하면 되는 것 아닌가하는 의문이 들 수 있다.

하지만, 만약 이렇게 다이아몬드 형태라면 해당 별똥별에서 탐색 시 그림에서처럼 회색 범위를 탐색할 수가 없는 문제가 생긴다.

 

 

 

아래는 소스 코드이다.

 

---

소스 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class B14658_하늘에서별똥별이빗발친다 {

    static int N ,M, L, K;
    static List<int[]> stars = new ArrayList<>();
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        input();
        int max = -1;
        for(int i = 0; i<K;i++){
            for(int j = 0; j<K;j++){
                int r = stars.get(i)[0];
                int c = stars.get(j)[1];
                max = Math.max(countStar(r, c), max);
            }
        }
        int answer = K-max;
        System.out.println(answer);
    }
    static int countStar(int r, int c){
        int cnt = 0;
        for(int k = 0; k<K;k++){
            int starR = stars.get(k)[0];
            int starC = stars.get(k)[1];
            if(r<=starR&&starR<=r+L && c<=starC&&starC<=c+L) cnt++;
        }
        return cnt;
    }

    static void input(){
        N = sc.nextInt();
        M = sc.nextInt();
        L = sc.nextInt();
        K = sc.nextInt();

        for(int i = 0; i<K;i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            stars.add(new int[]{x,y});
        }
    }
}