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

백준 14658: 하늘에서 별똥별이 빗발친다.

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

풀이

• 별 두개를 골라 y, x 중 더 작은 값 -> 별 두개를 모두 포함하는 좌표를 꼭짓점으로 지정해 계산
• 해당 꼭짓점을 기준으로 사분면 두개만 확인

package algorithm2023.oct.day22;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class BOJ_14658_하늘에서별똥별이빗발친다 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	
	
	
	static int N,M,L,K;
	static ArrayList<Star> stars = new ArrayList<>();
	
	static class Star{
		int x, y;

		public Star(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
		
		
		
	}
	public static void main(String[] args) throws Exception{
		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 Star(x,y));
		}
		
		//getAns()는 트램펄린이 튕겨내는 별의 개수를 리턴하므로 바닥에 떨어진 별을 카운트하기 위해 K_getAns()출력
		System.out.println(K-getAns());
		
		
	}
	
	
	static int getAns() {
		//최댓값을 구해야 함.
		int max = 0;
		//1번 별
		for(Star s : stars) {
			//2번 별
			for(Star s2 : stars) {
				//두 별을 모두 포함하는 왼쪽 위 꼭짓점을 구하기 위해 math.min 사용
				int cnt1 = 0;
				int cnt2 = 0;
				int x = Math.min(s2.x, s.x);
				int y = Math.min(s2.y, s.y);
				//해당 꼭짓점을 기준으로 했을 때 s3을 포함하는지 확인
				for(Star s3 : stars) {
					
					if(s3.x>=x&&s3.x-x<=L) {
						if(s3.y>=y&&s3.y-y<=L) {
							cnt1++;
						}
						else if(y>s3.y&&y-s3.y<=L) {
							cnt2++;
						}
					}
				}
				max = Math.max(max, Math.max(cnt1, cnt2));
				
				
			}
				
			
		}
		return max;
	}
}

---

Issue

• 처음엔 별 하나를 꼭짓점으로 잡았지만 실패

•               *
  
  
  
    *						*
  
  
  
                *
  

• 위와 같은 형태 못 잡음