백준 14658 JAVA

문제 유형

• 완전 탐색

문제 설명

• map의 크기 N*M
• 트램펄린의 크기 L*L
• K개의 별똥별 x,y 좌표가 주어짐
• 트램펄린의 범위 안에 별똥별이 포함될 시, 별똥별은 삭제됨

문제 접근

• 답
  • 트램펄린이 막아내지 못한 별똥별 개수
• 주어지는 정보
  • 별똥별 최대 개수 100개
• 정보 정리
  • A 별똥별을 트램펄린 시작지점의 x 좌표로 지정
  • B 별똥별을 트램펄린 시작지점의 y 좌표로 지정
    • K*K = 최대 10,000
  • 트램펄린 안에 별똥별이 몇개 들어가는지 확인
    • 연산 최대 100
  • 총합
    • 10,000*100 = 1,000,000
  • ⇒1초 미만이므로 완전탐색 가능
• 풀이
  •  
  • Why)
    • 왜 A, B 별똥별로 트램펄린의 시작지점을 정하는가?
      • 우리는 최대한 많이 모여있는 별똥별 위치에 트램펄린을 배치해야 한다.

                         

• 그렇다면, 우리는 최대한 바깥쪽에 있는 별이 트램펄린의 모서리에 가깝게 배치해야한다.
• 따라서 위 그림과 같이, 동그라미 된 제일 바깥쪽에 위치한 별의 x,y좌표에 트램펄린을 배치해야한다.

 

import java.util.*;
import java.io.*;

class Star
{
    public int y,x;
    
    public Star(int y, int x)
    {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static int[] star;
    static int[] dp;
    static int N,M,L,K;
    static List<Star> starList = new ArrayList<>();
    
    public static int SetTramp(int y, int x)
    {
        int cnt = 0;
        for(int i = 0; i<K; i++)
        {
            Star star = starList.get(i);
            
            if(star.y >= y && star.y <= y+L && star.x >= x && star.x <= x+L)
            {
                cnt++;
            }
        }
        
        return cnt;
    }
    
    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());
        
        star = new int[N+1];
        
        for(int i = 0; i<K; i++)
        {
            st = new StringTokenizer(br.readLine());

            int x,y;
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            
            starList.add(new Star(y,x));
        }
        
        int result = 0;
        for(int i = 0; i<K; i++)
        {
            Star star1 = starList.get(i);
            for(int j = 0; j<K; j++)
            {
                Star star2 = starList.get(j);
                result = Math.max(result,SetTramp(star2.y,star1.x));
            }

        }
        System.out.println(K-result);
    }
}