[BOJ] 1451 - 직사각형으로 나누기

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

BOJ - 직사각형으로 나누기

문제 유형: 누적합, 브루트 포스, 많은 조건 분기

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 128MB

 

문제

세준이는 N*M크기로 직사각형에 수를 N*M개 써놓았다.

세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다.

어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오.

 

입력

첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다.

 

출력

세 개의 작은 직사각형의 합의 곱의 최댓값을 출력한다.

 

풀이

sums[i][j] = (0, 0)부터 (i, j)까지의 누적합이라고 하자.

3개의 직사각형으로 분할하는 경우는 아래와 같이 6가지가 있다:

각 조건에 맞게 sums 누적합을 이용해서, 빠르게 직사각형별 숫자 합을 구할 수 있다.

가장 큰 곱을 반환해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

#define ll long long
using namespace std;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> mat(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        for (int j = 0; j < m; j++) {
            mat[i][j] = temp[j] - '0';
        }
    }

    vector<vector<int>> sums(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) {
                sums[i][j] = mat[i][j];
            } else if (i == 0) {
                sums[i][j] = sums[i][j - 1] + mat[i][j];
            } else if (j == 0) {
                sums[i][j] = sums[i - 1][j] + mat[i][j];
            } else {
                sums[i][j] = sums[i - 1][j] + sums[i][j - 1] -
                             sums[i - 1][j - 1] + mat[i][j];
            }
        }
    }

    ll ans = -1e9;
    // Case 0: 가로로 나란히
    if (m >= 3) {
        for (int j = 0; j < m - 2; j++) {
            int f = sums[n - 1][j];
            for (int secondEnd = j + 1; secondEnd < m - 1; secondEnd++) {
                int s = sums[n - 1][secondEnd] - f;
                int t = sums[n - 1][m - 1] - (s + f);
                ans = max(ans, 1LL * f * s * t);
            }
        }
    }
    // Case 1: 세로로 나란히
    if (n >= 3) {
        for (int i = 0; i < n - 2; i++) {
            int f = sums[i][m - 1];
            for (int secondEnd = i + 1; secondEnd < n - 1; secondEnd++) {
                int s = sums[secondEnd][m - 1] - f;
                int t = sums[n - 1][m - 1] - (s + f);
                ans = max(ans, 1LL * f * s * t);
            }
        }
    }
    if (n >= 2 && m >= 2) {
        // Case 2: 가로2,  세로1
        // Case 3: 세로1,  가로2
        for (int rightEnd = 0; rightEnd < m - 1; rightEnd++) {
            int t = sums[n - 1][m - 1] - sums[n - 1][rightEnd];
            for (int bottomBound = 0; bottomBound < n - 1; bottomBound++) {
                int f = sums[bottomBound][rightEnd];
                int s = sums[n - 1][rightEnd] - f;
                ans = max(ans, 1LL * f * s * t);
            }

            int f = sums[n - 1][rightEnd];
            for (int bottomBound = 0; bottomBound < n - 1; bottomBound++) {
                int s = sums[bottomBound][m - 1] - sums[bottomBound][rightEnd];
                t = sums[n - 1][m - 1] - (f + s);
                ans = max(ans, 1LL * f * s * t);
            }
        }
        // Case 4:  가로1밑에 세로2
        // Case 5: 세로2 밑에 가로1
        for (int bottomBound = 0; bottomBound < n - 1; bottomBound++) {
            int f = sums[bottomBound][m - 1];
            for (int rightEnd = 0; rightEnd < m - 1; rightEnd++) {
                int s = sums[n - 1][rightEnd] - sums[bottomBound][rightEnd];
                int t = sums[n - 1][m - 1] - (f + s);
                ans = max(ans, 1LL * f * s * t);
            }

            int t = sums[n - 1][m - 1] - sums[bottomBound][m - 1];
            for (int rightEnd = 0; rightEnd < m - 1; rightEnd++) {
                f = sums[bottomBound][rightEnd];
                int s = sums[bottomBound][m - 1] - f;
                ans = max(ans, 1LL * f * s * t);
            }
        }
    }

    cout << ans << "\n";

    return 0;
}