욱제는 하늘을 발로 차버렸다. 그랬더니 정말 별이 떨어졌다. 그런데, 정말로 별이 지구로 떨어지기 시작했다. 욱제는 지구를 지키는 정의의 용사가 되기로 결심했다.
"자기야, 나 세계를 지키고 올게. 꼭 돌아올 테니 조금만 기다려줘."
지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 L x 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)
#️⃣ 출력
욱제가 트램펄린으로 최대한 많은 별똥별을 튕겨낼 때, 지구에 부딪히는 별똥별의 개수를 출력한다.
✅ 풀이 Point
⛔ 완전탐색 문제 But, 입력값 500,000 → int[ ][ ] arr = new int[500_001][500_001]; 메모리 초과 슬라이딩 윈도우처럼 트램펄린이 설치될 수 있는 모든 구역 탐색시 시간 초과
⛔ 별 좌표를 중심으로 제 1, 2, 3, 4 사분면으로 나눠서 살펴볼 때 아래의 경우에는 탐색하지 못함.
트램펄린이 아래와 같이 위치할 경우, 모든 별 트램펄린 위에 있을 수 있음.
1️⃣ 트램펄린 위치 선정 → 트램펄린 위에 위치한 별 개수 확인
별이 최대한 트램펄린 모서리에 많이 위치할수록 좋음.
별의 개수가 100개 이하로 들어오기 때문에 별을 기준으로 완전 탐색 ➡️ 트램펄린의 왼쪽 상단 꼭짓점의 위치 = (기준 별 x좌표, 다른 별 y좌표) 로 하여 모두 탐색 (아래의 그림 참고, 기준 별 좌표 = (4, 7))
// main function
int cnt = 0;
for (int i = 0; i < K; i++) {
Node star1 = stars.get(i);
for (int j = 0; j < K; j++) {
Node star2 = stars.get(j);
cnt = Math.max(countStar(star1.x, star2.y), cnt);
}
}
private static int countStar(int x, int y) {
int temp = 0;
for (int k = 0; k < K; k++) {
Node star = stars.get(k);
// star는 x, y가 N, M을 넘지 않음. → x + L이 N보다 커지는 경우 고려할 필요 x
if (x <= star.x && star.x <= x + L && y <= star.y && star.y <= y + L) temp++;
}
return temp;
}
✅ 정답
import java.io.*;
import java.util.*;
public class Main {
static int N, M, L, K;
static ArrayList<Node> stars = new ArrayList<>();
static public class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
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());
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 Node(x, y));
}
int cnt = 0;
for (int i = 0; i < K; i++) {
Node star1 = stars.get(i);
for (int j = 0; j < K; j++) {
Node star2 = stars.get(j);
cnt = Math.max(countStar(star1.x, star2.y), cnt);
}
}
System.out.println(K - cnt);
}
private static int countStar(int x, int y) {
int temp = 0;
for (int k = 0; k < K; k++) {
Node star = stars.get(k);
// star는 x, y가 N, M을 넘지 않음. → x + L이 N보다 커지는 경우 고려할 필요 x
if (x <= star.x && star.x <= x + L && y <= star.y && star.y <= y + L) temp++;
}
return temp;
}
}
