Codeforces Round #745 (Div. 2)-C. Portal

문제 설명

이브는 $n \times m$ 크기를 가진 직사각형 $A$를 발견했다. 이 직사각형은 $n$ 개 행과 $m$ 개 열의 블록으로 이루어져 있다. 직사각형을 이루는 각 블록은 흑요석블록이거나 비어있다. 이브는 한번에 빈 블록을 흑요석 블록으로 바꾸거나, 흑요석 블록을 빈 블록으로 바꿀 수 있다.

크기 $a \times b$ 인 직사각형 $M$은 다음 조건을 모두 만족하면 포탈이다.

• $a \ge 5, b \ge 4$
• 모든 $x(1 < x < a)$에 대해서 블록 $M_{x, 1}$ 과 $M_{x, b}$는 흑요석 블록이다.
• 모든 $x(1 < x < b)$에 대해서 블록 $M_{1, x}$ 과 $M_{a, x}$는 흑요석 블록이다.
• 모든 $x(1 < x < a), y(1 < y < b)$에 대해서 블록 $M_{x, y}$는 빈 블록이다.
• $M_{1, 1}, M_{1, b}, M_{a, 1}, M_{a, b}$는 아무거나 상관없다.

무조건 $a$개 행과 $b$개 행이어야 하며, 모서리는 아무거나 상관 없다.

이브는 포탈 1개를 만들기 위해서 필요한 최소 연산 횟수를 구하고 싶다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (t \ge 1)$이 주어진다.

각 테스트 케이스의 첫번째 줄은 두 정수 $n$과 $m (5 \le n \le 400, 4 \le m \le 400)$ 이 주어진다.

그리고 $n$줄에 걸쳐서 각 줄에는 $m$개의 $0$과 $1$로 이루어진 문자열이 주어진다. 만약 $i$번째 줄에 $j$번째 문자가 $0$이라면 블록 $A_{i, j}$는 빈 블록이고, 아니면 $A_{i, j}$는 흑요석 블록이다.

Output
각 테스트 케이스마다 답을 출력한다.

Example
input
2
5 4
1000
0000
0110
0000
0001
1
9 9
001010001
101110100
000010011
100000001
101010101
110001111
000001111
111100000
000110000

output
12
5

문제 접근

사용한 알고리즘: 브루트 포스, 다이나믹 프로그래밍, 부분합
걸린 시간 : 00:23
2차원 배열의 부분합 알고리즘을 까먹은 대가를 혹독히 치르게한 문제였다. 그리고 시간을 줄이는 것이 얼마나 어려운지도 다시 한번 느끼게한 거지같은 문제였다. 괜히 1700점 짜리 문제가 아닌것 같다.

일단 2차원 배열의 부분합 알고리즘을 모르는 사람은 그거 부터 공부하고 와야한다. 400 * 400 = 160000크기 배열을 완전탐색을 해야하기 때문에 다이나믹 프로그래밍 아니면 그냥 못푼다. 하지만 희망적인 소식은 이것만 알고 간단한 조건문 하나만 추가하면 문제는 의외로 쉽게 풀린다.

editorial에서 나온 방식은 내가 이해를 못했기 때문에 내가 푼 방식과 유사한 오렌지 유저의 코드를 보고 이해를 했다.

일단 먼저 $(i, j)$까지 누적합을 저장하는 배열 dp와, $(lx, ly)$ 부터 $(rx, ry)$까지 부분합을 계산하는 함수 getSum을 만든다. 그리고 문제에서 주어진 포탈의 조건을 만족하는 값을 왼쪽, 오른쪽, 위, 아래 모두 계산하고 마지막으로 가운데까지 계산해서 모두 더한다.

왼쪽에 있는 값을 예시로 한번 계산해 보자. 좌상향 좌표를 (i, j), 우하향 좌표를 (a, b)라고 가정하자. 그렇다면 포탈의 왼쪽 부분에 존재하는 흑요석 블록의 개수는 getSum(i + 1, j, a - 1, j)일 것이다. 따라서 흑요석 블록으로 바꿔야할 빈 블록의 개수는 a - i - 1 - getSum(i + 1, j, a - 1, j)이다. 이런식으로 포탈의 왼쪽, 오른쪽, 위, 아래 부분을 구하고, 가운데 부분을 구하면 된다. 이때 가운데 부분은 약간 방식이 다른데, 가운데 부분은 빈 블록으로만 이루어져야 하기 때문에 흑요석 블록의 개수만 세면 된다.

위에서 구한 모든 값을 계산하고 최솟값을 계속 갱신하면 되는데 여기서 문제가 발생한다. 문제에서 주어지는 제한시간은 1초인데, 4중 for문을 사용하기 때문에 그냥 반복문을 돌리면 무조건 시간초과가 나서 주의가 필요하다.

포탈 크기가 최소일때 나올 수 있는 연산의 최대 경우를 생각해보자. 포탈 크기는 5 * 4 = 20 이며, 왼쪽, 오른쪽에 모두 빈 블록이 있을 경우 3 * 2 = 6이고 위, 아래에 모두 빈 블록이 있을 경우 2 * 2 = 4이고 가운데 공간이 모두 흑요석 블록으로 채워져있으면 3 * 2 = 6개의 연산이 모두 추가로 필요하다. 즉 최대 경우는 6 + 6 + 4 = 16이다. 그렇다면 어떠한 경우라도 답이 16보다는 작거나 같지 않을까? 따라서 우리가 왼쪽위에서 시작하기 때문에 왼쪽하고 위쪽에서 구한 값이 16이 넘어버리면 그 이후는 절대 답이 될 수 없기 때문에 break를 해준다. 그리고 이 방법이 이 문제의 핵심이다.

정답 코드

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[402][402];

int getSum(int lx, int ly, int rx, int ry){
    return dp[rx][ry] - dp[rx][ly - 1] - dp[lx - 1][ry] + dp[lx - 1][ly - 1];
}

int main() {
    int t; scanf("%d", &t);
    while(t--){
        int n, m; scanf("%d %d", &n, &m);
        char str[402];
        for(int i = 1; i <= n; i++){
            scanf("%s", str + 1);
            for(int j = 1; j <= m; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (str[j] == '1');
            }
        }

        int ans = 987654321;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                for(int a = i + 4; a <= n; a++){
                    for(int b = j + 3; b <= m; b++){
                        int l = a - i - 1 - getSum(i + 1, j, a - 1, j);
                        int r = a - i - 1 - getSum(i + 1, b, a - 1, b);
                        int u = b - j - 1 - getSum(i, j + 1, i, b - 1);
                        int d = b - j - 1 - getSum(a, j + 1, a, b - 1);
                        int m = getSum(i + 1, j + 1, a - 1, b - 1);
                        if(l >= 16 || u >= 16) break;
                        ans = min(ans, l + r + u + d + m);
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}