BOJ) 보석

보석

2492번: 보석

정말 어려운 문제였다.

M by N 크기의 map이 주어지는데, 이 맵에 금강석이 묻혀있는 정보가 주어진다.

n과 m은 1 ~ 1,000,000의 숫자로 주어지고, 금강석은 최대 100개 까지 주어진다.

또한, 정사각형의 한 변의 길이가 되는 k가 주어지는데, 이 정사각형을 임의로 맵에 그렸을 때, 가장 많은 금강석을 갖게되는 정사각형의 왼쪽 위 꼭짓점의 위치와 금강석의 개수를 출력하는 문제다.

 

우선, 이 문제가 슬라이딩 윈도우로 분류되어 있어서 이를 이용해서 접근하려고 했었다.

세로의 최대 크기만큼 List를 선언하고, y축에 해당하는 금강석의 x좌표를 저장했다.이후, 반복문을 돌면서 금강석이 나타나면 해당 금강석의 좌표를 정사각형 안의 모든 구역에 존재하도록 모든 경우의 수를 돌렸다.

 

구현하면서도 이건 진짜 아닌데.. 하는 생각이 들어서 코드를 전부 지웠다.이후 많은 고민을 했는데, 정사각형의 좌표를 어떻게 잡아야하는지 감이 오지 않아서 다른 풀이를 참고했다. 이 블로그에는 풀이에 대한 간략한 설명을 담고 있었다.

 

금강석의 최대 갯수가 100이라는 아주 작은 수로 주어지기 때문에, 이를 반복해서 돌면서 금강석 두개를 짝지어 첫번째 금강석의 x좌표와 두번째 금강석의 y좌표 위치에서 직사각형을 그려준다.만약, 각 금강석의 위치가 x와 y의 최댓 값을 벗어난다면, 정사각형이 각 최댓값을 테두리로 갖도록 좌표를 설정해준다.이후, 해당 x좌표와 y좌표가 좌측 하단으로 그려지는 정사각형 안에 포함되는 금강석의 개수를 찾아준다.구한 개수와 최댓값을 비교하면서 값을 최신화 시켜주고, 답이 될 정사각형의 좌측 상단 모서리 좌표를 저장하기 위해 탐색을 시작한 (x,y) 좌표를 -> (x, y+k) 좌표로 저장해준다.

 

얼핏보면 굉장히 짧고 쉬운 로직인 것 같지만, 짧은 시간 안에 당황하지 않고 로직을 떠올리기 어렵다고 생각한다. 슬라이딩 윈도우의 가장 큰 장점은 이전 값에 대한 메모이제이션인데, 어떻게 하면 이전 값을 가지고 탐색할 수 있을지 아직 잘 모르겠다. 하지만, 탐색의 기준이 되는 k가 100이라는 작은 숫자이기 때문에 브루트 포스도 괜찮다고 생각이 든다.

 

코드

 

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

public class Jewelry_2492 {
  static final String NEW_LINE = "\n", SPACE = " ";
  static int width,height,t,k;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    width = Integer.parseInt(st.nextToken());
    height = Integer.parseInt(st.nextToken());
    t = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());

    Pos[] jewelryArr = new Pos[t];
    for(int i=0; i<t; i++) {
      st = new StringTokenizer(br.readLine());
      jewelryArr[i] = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }
    br.close();
    solution(jewelryArr);
  }

  private static void solution(Pos[] jewelryArr) {
    int max = 0;
    Pos maxPos = new Pos(0,0);

    for(int i=0; i<t; i++) {
      for(int j=0; j<t; j++) {
        int x = jewelryArr[i].x + k > width ? width - k : jewelryArr[i].x;
        int y = jewelryArr[j].y + k > height ? height - k : jewelryArr[j].y;

        int count = getCount(x,y,jewelryArr);
        if(count > max) {
          max = count;
          maxPos.x = x;
          maxPos.y = y+k;
        }
      }
    }
    StringBuilder sb = new StringBuilder();
    sb.append(maxPos.x).append(SPACE).append(maxPos.y).append(NEW_LINE);
    sb.append(max);

    System.out.println(sb.toString());
  }

  private static int getCount(int x, int y, Pos[] jewelryArr) {
    final int MAX_X = x+k, MAX_Y = y+k;
    int count =0;
    for(Pos jewelry : jewelryArr) {
      if(x <= jewelry.x && jewelry.x <=MAX_X && y <= jewelry.y && jewelry.y <= MAX_Y) {
        count++;
      }
    }
    return count;
  }

  private static class Pos {
    int x, y;
    public Pos(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
}