10 Apr 2023

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

14658

풀이 방법

도저히 해결 방법을 몰라서 참고한 문제이다.

두 별의 꼭지점을 만들어 트램펄린을 펴는게 가장 좋다고 한다. (논리적인 이유는 찾지 못했음)

그렇기 때문에 별1.x, 별2.y / 별2.x, 별2.y로 묶으면 된다. 대략적으로 아래 그림과 같다.

boj14658_1

먼저 N과 M(맵의 크기)이 L(트램펄린 크기)보다 작다면 무조건 막을 수 있으므로 0개로 출력했다.

그리고 맵의 숫자가 크다보니(<=500000) 이중배열을 맵으로 만들면 시간 초과가 난다는 점을 유의해야한다.

시작은 N과 M(맵의 크기)이 L(트램펄린 크기)보다 작다면 무조건 막을 수 있으므로 0개로 출력하고 나머지는 두 별을 잇고 트램펄린을 펴는 동작을 반복하면 끝.

풀이 코드

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

public class BOJ_14658_하늘에서_별똥별이_빗발친다 {
	static class Star {
		int r;
		int c;
		
		Star(int r, int c){
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "ShootingStar [r=" + r + ", c=" + c + "]";
		}
		
	}
	static int N, M, L;
	static Star[] 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()); // 트럼펠린 크기(l x l)
		int K = Integer.parseInt(st.nextToken()); // 별똥별 수
		stars = new Star[K];
		
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			
			stars[i] = new Star(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); // 별똥별 입력
		}
		
		if(N<=L && M<=L) {
			System.out.println(0); 
			return;
		}
		
		int ans = 0;
		for(int i=0; i<stars.length; ++i) {
			for(int j=0; j<stars.length; ++j) {				
				ans = Math.max(ans, check(stars[i].r, stars[j].c));
				ans = Math.max(ans, check(stars[i].c, stars[j].r));
			}
		}
		
		System.out.println(K-ans);
	}
	private static int check(int x, int y) {
		int count = 0;
		
		for(Star s : stars) {
			if(s.r>=x && s.r<=x+L && s.c>=y && s.c<=y+L) {
				count++;
			}
		}
		
		return count;
	}

}

Thank You For Reading

점점 강해지고 있습니다.