백준 1451 : 직사각형으로 나누기

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

1. 접근

• 직사각형을 나누는 과정에서 무조건 가로를 1~m, 세로를 1~n까지 돌려보아야 한다
  => 완전탐색, 브루트포스 brute force 문제
• 이 문제의 경우 2차원 배열을 쓰게되므로 코드를 짜기 굉장히 복잡해 보인다.
• 그러나, 여러 테스트를 돌려보면 직사각형 3개가 나오는 모양이 6개의 패턴으로 정해져 있음을 알 수 있다.
• col을 3개로 나누는 경우, 자르는 곳의 인덱스를 i, j로 두고 절단한다. 각각의 값을 증가시켜가면서 경우의 수를 구한다.
• ㅗ 모양으로 자르는 경우, row를 i만큼 자르고, col을 j만큼 자른다.
• sum 함수를 통해 간단하게 배열의 합을 구할 수 있다.

2. 나의 풀이

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;

int arr[MAX][MAX];
int n, m;
long long maxval=0; //모든 값이 9인 경우 long long 값이 필요함

long long sum(int sr, int sc, int er ,int ec) {
	long long ret = 0;
	for (int i = sr; i <= er; i++) {
		for (int j = sc; j <= ec; j++) {
			ret += arr[i][j]; 
		}
	}
	return ret;
}

void col_divide() { //col 을 나눔
	if (m < 3)	return;
	for (int i = 0; i < m - 2; i++) {
		for (int j = i+1; j < m - 1 - i; j++) {
			long long a = sum(0, 0, n-1, i);
			long long b = sum(0, i + 1, n-1, j);
			long long c = sum(0, j + 1, n-1, m - 1);
			if (maxval < a * b * c)
				maxval = a * b * c;
		}
	}
	return;
}

long long row_divide() { //row를 나눔
	if (n < 3)	return 0;	
	for (int i = 0; i < n - 2; i++) {
		for (int j = i + 1; j < n - 1 - i; j++) {
			long long a = sum(0, 0, i, m-1);
			long long b = sum(i+1, 0, j,m-1);
			long long c = sum(j+1, 0, n - 1, m - 1);
			if (maxval < a * b * c)
				maxval = a * b * c;
		}
	}
	return maxval;
}

void bigcol_divide() { //가로로 긴 직사각형이 하나 있음
	if (n < 2 || m < 2)	return;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m - 1; j++) {
			//ㅗ 모양
			long long a = sum(0, 0, i, j);
			long long b = sum(0, j+1, i, m - 1);
			long long c = sum(i+1, 0, n - 1, m - 1);
			if (maxval < a * b * c)
				maxval = a * b * c;

			a = 0; b = 0; c = 0;
			//ㅜ 모양
			a = sum(0, 0, i, m-1);
			b = sum(i+1, 0, n-1, j);
			c = sum(i + 1, j+1, n - 1,m - 1);
			if (maxval < a * b * c)
				maxval = a * b * c;
		}
	}
	return;
}

void bigrow_divide() {//세로로 긴 직사각형이 하나 있음
	if (n < 2 || m < 2)	return;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m - 1; j++) {
			//ㅓ 모양
			long long a = sum(0, 0, i, j);
			long long b = sum(i+1, 0, n-1, j);
			long long c = sum(0, j+1, n - 1, m - 1);
			if (maxval < a * b * c)
				maxval = a * b * c;

			a = 0; b = 0; c = 0;
			//ㅏ 모양
			a = sum(0, 0, n-1, j);
			b = sum(0, j+1, i, m-1);
			c = sum(i+1, j+1, n - 1, m - 1);
			if (maxval < a * b * c)
				maxval = a * b * c;
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		char tem[51];
		cin >> tem;
		for (int j = 0; j < m; j++) {
			arr[i][j] = tem[j] - '0';
		}
	}
	col_divide();
	row_divide();
	bigcol_divide();
	bigrow_divide();

	cout << (long long)maxval << "\n";
	return 0;
}

3. 참고

https://dbstndi6316.tistory.com/116
sum 함수를 사용한 풀이법

https://www.acmicpc.net/board/view/60463
반례 모음

---

sum함수 안만들고 일일이 다 구했다가 3퍼센트에서 계속 오답이 나왔다..
sum함수를 쓰는방식으로 수정했더니 정답 처리가 되었다...
원래 방법은 도대체 어디서 잘못된걸까....