[BOJ 1451 // C++] 직사각형으로 나누기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1451번 문제인 직사각형으로 나누기이다.
문제는 아래 링크를 확인하자.

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

 

어떤 직사각형을 두 개의 직사각형으로 나누는 방법은 가로방향이나 세로방향으로 한 번 자르는 것 외에는 없다. 그리고 세 개의 직사각형으로 나누는 방법은 (1)가로 방향이나 세로 방향으로 두 번 자르거나 (2) 가로 방향으로 한 번 자르고 그 결과로 나온 직사각형 중 하나를 세로로 한 번 자르거나 (3) 세로 방향으로 한 번 자르고 그 결과로 나온 직사각형 중 하나를 가로로 한 번 자르는, 총 세 가지 외에는 없다.

 

위의 관찰을 이용하여 자를 수 있는 모든 방법에 대하여 직사각형의 합의 곱을 계산해 그 중 최댓값을 구하자. 2차원 누적 합 배열을 이용하면 위의 계산을 효율적으로 할 수 있을 것이다.

#include <iostream>
using namespace std;
typedef long long ll;

int R, C; ll ans;
ll A[51][51];

ll func(int r1, int c1, int r2, int c2) {
    return A[r2][c2] - A[r1 - 1][c2] - A[r2][c1 - 1] + A[r1 - 1][c1 - 1];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            char x; cin >> x;
            A[r][c] += x - '0';
            A[r][c] += A[r - 1][c] + A[r][c - 1] - A[r - 1][c - 1];
        }
    }
    for (int r1 = 1; r1 < R; r1++) {
        for (int r2 = r1 + 1; r2 < R; r2++) {
            ans = max(ans, func(1, 1, r1, C) * func(r1 + 1, 1, r2, C) * func(r2 + 1, 1, R, C));
        }
    }
    for (int c1 = 1; c1 < C; c1++) {
        for (int c2 = c1 + 1; c2 < C; c2++) {
            ans = max(ans, func(1, 1, R, c1) * func(1, c1 + 1, R, c2) * func(1, c2 + 1, R, C));
        }
    }

    for (int r = 1; r < R; r++) {
        for (int c = 1; c < C; c++) {
            ans = max(ans, func(1, 1, r, c) * func(1, c + 1, r, C) * func(r + 1, 1, R, C));
            ans = max(ans, func(1, 1, r, C) * func(r + 1, 1, R, c) * func(r + 1, c + 1, R, C));
        }
    }
    for (int c = 1; c < C; c++) {
        for (int r = 1; r < R; r++) {
            ans = max(ans, func(1, 1, r, c) * func(r + 1, 1, R, c) * func(1, c + 1, R, C));
            ans = max(ans, func(1, 1, R, c) * func(1, c + 1, r, C) * func(r + 1, c + 1, R, C));
        }
    }
    cout << ans;
}

 

아래는 제출한 소스코드이다.