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

문제 링크

문제#

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

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

“에이, 거짓말!”

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

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

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

지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 $L \times L$ 크기의 트램펄린을 준비했다. 별똥별이 어디로 떨어질지는 이미 알고 있기 때문에, 욱제는 이 트램펄린으로 최대한 많은 별똥별을 우주로 튕겨낼 계획이다. 하지만 학교 예산으로 트램펄린을 구매하는 욱제는 이 긴급한 와중에도 예산 심의 통과를 기다리느라 바쁘다!

욱제를 도와 세계를 구하자. 최대한 많은 별똥별을 튕겨내도록 트램펄린을 배치했을 때, 지구에는 몇 개의 별똥별이 부딪히게 될까? (별똥별이 떨어지는 위치는 겹치지 않으며 별똥별은 트램펄린의 모서리에 부딪혀도 튕겨나간다!) 트램펄린은 비스듬하게 배치 할 수 없다.

입력#

첫째 줄에 네 정수 $N$, $M$, $L$, $K$가 주어진다. $(1 \le N, M \le 500{,}000,\ 1 \le L \le 100{,}000,\ 1 \le K \le 100)$ $N$은 별똥별이 떨어지는 구역의 가로길이, $M$은 세로길이, $L$은 트램펄린의 한 변의 길이, $K$는 별똥별의 수를 뜻한다. 이후 $K$개의 줄에 걸쳐 별똥별이 떨어지는 위치의 좌표 $(x, y)$가 주어진다. $(0 \le x \le N,\ 0 \le y \le M)$

출력#

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

풀이#

트램펄린은 축에 평행한 $L \times L$ 정사각형이고, 별똥별 수 $K$가 최대 100이라 완전탐색이 가능하다. 최적 위치의 왼쪽 경계는 어떤 별의 $x$좌표에, 아래쪽 경계는 어떤 별의 $y$좌표에 맞춰도 손해가 없다.

코드에서는 모든 별 $i$의 $x$좌표와 모든 별 $j$의 $y$좌표를 조합해 트램펄린의 시작점으로 삼는다. 그 위치에서 $x$가 startX부터 startX + L 사이이고, $y$가 startY부터 startY + L 사이인 별의 개수를 센다.

가장 많이 튕겨낸 별의 수를 구한 뒤 전체 별똥별 수 $K$에서 빼면 지구에 부딪히는 별똥별 수가 된다.

코드#

import java.io.*;
import java.util.*;
 
public class Main {
	
	static class Star {
		int x, y;
		Star(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static Star[] stars;
	
	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());
		stars = new Star[K];
 
		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[i] = new Star(X, Y);
		}
		
		System.out.println(solve(N, M, L, K));
	}
	
	static int solve(int N, int M, int L, int K) {
		int ans = 0;
		for (int i = 0; i < K; i++) {
			for (int j = 0; j < K; j++) {
				ans = Math.max(ans, countStar(stars[i].x, stars[j].y, stars[i].x + L, stars[j].y + L));
			}
		}
		return K - ans;
	}
	
	static int countStar(int startX, int startY, int endX, int endY) {
		int sum = 0;
		for(Star star : stars) {
			if (star.x >= startX && star.x <= endX 
					&& star.y >= startY && star.y <= endY)
				sum++;
		}
		return sum;
	}
	
}

복잡도#

• 시간 복잡도: 후보 위치 $K^2$개마다 별 $K$개를 세므로 $O(K^3)$이다.
• 공간 복잡도: 별 좌표 배열로 $O(K)$를 사용한다.

마무리#

별 좌표 두 개를 경계로 잡는다는 관찰 덕분에 넓은 하늘도 작은 완전탐색으로 줄어든다. 가장 많이 덮는 위치만 찾으면 남은 별똥별 수는 전체에서 빼면 된다.