[BOJ 25174] 백준 25174번 - 힘겨운 쿠기의 식당 개업기

May 18, 2022

1. 문제

백준 25174번 - 힘겨운 쿠기의 식당 개업기 (https://www.acmicpc.net/problem/25174)

$X$와 $Y$의 범위는 $-100,000,000$부터 $100,000,000$까지인데 $N\leq 1000$이라서, 좌표 압축을 사용하여 $N^2$ 탐색이 가능하도록 만들 수 있다.

$X$축 기준과 $Y$축 기준으로 각각 정렬을 사용해서 새로운 인덱싱을 하는 방식으로 좌표 압축을 진행한다.

그런 다음, $(1, 1)$을 왼쪽 위, $(y, x)$를 오른쪽 아래 꼭짓점으로 하는 직사각형 부분의 넓이를 dp[y][x]에 저장하는 다이나믹 프로그래밍 코드를 만들 수 있다.

(좌표 압축을 했을 때, y축 좌표의 최댓값을 maxy, x축 좌표의 최댓값을 maxx라 가정한다.)

for (int i = 0; i < maxy; i++) {
  for (int j = 0; j < maxx; j++) {
    dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + Z[i][j];
  }
}

그리고 이중 for문으로 특정 $y$축과 특정 $x$축의 기준점을 잡고 네 부분으로 나눈 후, 각 부분의 dp값의 합으로 최솟값을 갱신하면, 정답을 구할 수 있다.

$y=i$축과 $x=j$축으로 나누면,

이렇게 총 네 부분으로 나눌 수 있다. 이들의 최댓값과 최솟값의 차를 구할 수 있고, 모든 축에 대해 최솟값을 찾으면 정답이다.