[BOJ][Java] 2492. 보석

문제

https://www.acmicpc.net/problem/2492

 

문제 이해

• 가로 N, 세로 M인 지도 위에 금강석 T개의 좌표 (A, B)가 주어질 때,
  가장 많은 금강석을 포함하는 정사각형의 좌표와 포함 개수를 구한다.
• 정사각형의 변의 길이는 K이고, 꼭짓점은 정수 격자점에 있어야 한다.
• 정사각형 변 위의 금강석도 포함된 것으로 본다.

 

문제 풀이

메모리 초과

• 범위: 1 ≤ N, M ≤ 1,000,000, 1 ≤ T ≤ 100, 1 ≤ K ≤ N, M, 0 ≤ A ≤ N, 0 ≤ B ≤ M
• N, M이 최대 1e6이라 int[N+1][M+1] 같은 2차원 배열 생성은 불가능하다. (TB급 필요)
• 왼쪽아래 (x, y)를 x=0..N-K, y=0..M-K 전 범위로 전수 탐색하는 것도 불가능하다. (최악 1e12 후보)

 

보석이 있는 곳 기준으로 탐색

모든 금강석을 정사각형의 오른쪽 위 모서리 후보로 잡고, 해당 정사각형에 포함되는 금강석 수를 센다.

• rightX = gems[i].x, rightY = gems[j].y 조합을 모두 시도
• 정사각형이 범위를 벗어나는 경우(rightX - K < 0 또는 rightY - K < 0)에는 정사각형을 (0,0)으로 붙인다
• 검사 범위: [rightX - K .. rightX] × [rightY - K .. rightY]
• 이렇게 하면 전수 탐색 없이 후보 수를 O(T^2)로 줄이고,
  각 후보에서 금강석 T개만 세면 되므로 전체 시간복잡도는 O(T^3)(최대 100^3 = 1e6)이다.
• 메모리는 금강석 좌표 T개만 보관하므로 O(T)이다.

 

반례

정사각형이 범위를 벗어나는 경우를 처리해야 한다.

2 2 1 2
2 1

0 2
1

 

코드

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

public class Main {
    static class Point {
        int x, y;

        Point(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());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        Point[] gems = new Point[t];
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            gems[i] = new Point(x, y);
        }

        int maxCount = 0;
        Point ans = null;

        // 모든 금강석을 정사각형의 오른쪽 위 모서리로 정해서, 해당 정사각형에서 포함되는 개수 세기
        for (int i = 0; i < t; i++) {
            for (int j = 0; j < t; j++) {
                int rightX = gems[i].x;
                int rightY = gems[j].y;

                // 이 정사각형 안에서 금강석 개수 구하기
                int cnt = 0;
                for (int l = 0; l < t; l++) {
                    int x = gems[l].x;
                    int y = gems[l].y;

                    if (rightX - k < 0) {
                        rightX = k;
                    }

                    if (rightY - k < 0) {
                        rightY = k;
                    }

                    if (rightX - k <= x && x <= rightX && rightY - k <= y && y <= rightY) {
                        cnt++;
                    }
                }

                if (cnt >= maxCount) {
                    maxCount = cnt;
                    ans = new Point(rightX - k, rightY); // 왼쪽 위 좌표 저장
                }
            }
        }

        System.out.println(ans.x + " " + ans.y);
        System.out.println(maxCount);
    }
}