[자바] 백준 2190 - 점 고르기 2 (java)

목차

문제 : boj2190

 

 

필요 알고리즘

• 브루트 포스 (brute force)
  
  • 약간의 아이디어만 더해주면 그냥 브루트포스로 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  보통 2차원인 문제는 우선 1차원으로 생각해보면 접근하기 쉬운 경우가 많다. 이 경우에도 그냥 직선에 N개의 x좌표가 주어진다고 하고, 길이 A 짜리 막대로 가장 많은 점을 포함한다고 생각해보자. 이 경우 가장 간단한 방법은 N개의 점을 시작점으로 x+A 까지 모든 N개의 좌표를 확인하며 포함되는지 확인하면 된다. 이 경우 O(N^2)으로 풀이 가능하다.

 

  그런데 이 때 우린 직관적으로  좌표가 -20억~20억이라고 해서 -20억, -19억9999...9, -19억9999..8 처럼 40억개의 모든 좌표에서 막대를 놓으며 확인하지 않는다. 당연히 가장 많은 점을 포함하도록 막대를 놓는다면, 막대의 한쪽 끝은 입력으로 들어왔던 좌표들의 위치로 놓아보면 된다. 그래야 적어도 1개는 포함되니깐.

 

  그럼 이제 2차원으로 확장해보자. 똑같다. 직관적으로 적절한 곳에서 직사각형을 시작한다고 하자. 그리고 N개의 2차원 좌표를 모두 확인하면서 직사각형에 포함하는지 보면 된다. 근데 '적절한 곳'이 어딜까? 1차원 때 처럼 단순하게 직사각형의 좌측 상단을 점에두면 안된다. 각 x, y 좌표가 교차하는 곳에서 시작해줘야 한다.

 

  (1)을 보자. 2차원 평면에서 A=2, B=2 인 직사각형을 놓는다고 해보자. 1차원 때 처럼 각 점이 시작하는 곳을 본다면 2개가 최대이다. 하지만 실은 (2) 처럼 놓은 3개가 정답이다. 즉, (3)처럼 각 점에서 그은 직선이 서로 교차하는 모든 지점에서 직사각형을 만들어줘야 한다. 즉, 최대 N^2개의 교차점에서 N개의 모든 점을 살펴보면서 해당 지점에서 시작한 AxB 짜리 직사각형내에 점이 포함되는지 세주면 된다. O(N^3)이고, N이 100이므로 브루트포스로 시간은 충분하다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        long[][] arr = new long[n][2];
        Set<Long> xEx = new HashSet<>();
        Set<Long> yEx = new HashSet<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Long.parseLong(st.nextToken());
            arr[i][1] = Long.parseLong(st.nextToken());
            xEx.add(arr[i][0]);
            yEx.add(arr[i][1]);
        }

        int answer = 0;
        for (Long curX : xEx) {
            for (Long curY : yEx) {

                int cnt = 0;
                for (int i = 0; i < n; i++) {
                    if (arr[i][0] >= curX && arr[i][1] >= curY && arr[i][0] <= curX + a && arr[i][1] <= curY + b) {
                        cnt++;
                    }
                }
                answer = Math.max(answer, cnt);
            }
        }

        System.out.println(answer);
    }
}