C++ / 백준 / 1451 / 직사각형으로 나누기

문제

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

1451번: 직사각형으로 나누기

문제풀이

첫 번째 직사각형, 두 번째 직사각형이 될 수 있는 모든 경우를 구한다.

세 번째 직사각형은 첫 번째, 두 번째 직사각형을 만들 때 사용하지 않은 칸으로 만든다.

Div1은 첫 번째 직사각형, Div2는 두 번째 직사각형, Div3은 세 번째 직사각형을 만드는 함수이다.

먼저 첫 번째 직사각형을 만든다.

이중 for문을 돌려 y는 0부터 N까지, x는 0부터 M까지 돌게 한다.

x가 커지면서 이런 모양의 직사각형이 만들어진다.

y가 커지면서 이런 모양의 직사각형이 만들어진다.

x, y가 커지면서 이런 모양의 직사각형이 만들어진다.

 

Div1을 통해 직사각형을 만들었으면 Div2를 통해 두 번째 직사각형을 만들어야 한다.

두 번째 직사각형을 만들 때는 크게 보면 3가지, 세분화하면 총 6가지의 경우의 수로 나뉜다.

 

1) 첫 번째 경우

먼저 첫 번째 직사각형의 y가 N까지 채워졌을 때

아래의 그림처럼 두 가지 경우의 수가 있다.

 

1-1, 1-2)

직사각형의 좌표 x가 M인 경우, 직사각형의 y가 N인 경우이다.

 

2) 두 번째 경우

첫 번째 직사각형의 x가 M까지 채워졌을 때

아래의 그림처럼 두 가지 경우의 수가 있다.

 

2-1, 2-2)

직사각형의 좌표 y가 N인 경우, 직사각형의 좌표 x가 M인 경우이다.

3) 세 번째 경우

첫 번째 직사각형의 두 변모도 끝에 닿지 못했을 때이다.

이 경우에도 두 가지 경우의 수가 있다.

 

3-1, 3-2)

직사각형의 좌표 x가 M인 경우, 직사각형의 좌표 y가 N인 경우이다.

이렇게 두 번째 직사각형의 경우의 수를 구했으면 나머지 세 번째 직사각형을 구하는 함수 Div3으로 넘어간다.

Div3은 간단하다, 모든 좌표를 돌면서 방문하지 않은 곳이 있으면 해당 좌표의 값을 더한다.

그다음 Div1, Div2, Div3에서 구한 각각의 직사각형들의 누적합들을 곱하고 그중 최댓값을 출력한다.

 

Div함수는 이전 직사각형이 있다면 직사각형의 누적합을, 인자로 받는다.

그리고 이번 직사각형의 끝 지점의 최솟값, 끝 지점의 최댓값을 인자로 받는다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>>value;
int N, M;
long long answer;

void Div3(long long mul, vector<vector<bool>>visit) {
	int y = 0, x = 0;
	long long sum = 0;

	for (y = 0; y < N; ++y)
		for (x = 0; x < M; ++x)
			if (!visit[y][x])
				sum += value[y][x];

	answer = max(answer, mul * sum);
}

void Div2(long long mul, int s_y, int s_x, int e_y, int e_x, vector<vector<bool>>visit) {
	int y = 0, x = 0;
	long long sum = 0;
	for (y = s_y; y <= e_y; ++y)
		for (x = s_x; x <= e_x; ++x)
			if (!visit[y][x]) {
				sum += value[y][x];
				visit[y][x] = true;
			}

	Div3(mul * sum, visit);
}

void Div1(int s_y, int s_x, int e_y, int e_x, vector<vector<bool>>& visit) {
	int y = 0, x = 0;
	long long sum = 0;
	for (y = s_y; y <= e_y; ++y) {
		for (x = s_x; x <= e_x; ++x) {
			sum += value[y][x];
			visit[y][x] = true;
		}
	}
	if (e_y == N - 1 && e_x < M - 1) {
		for (y = 0; y < N - 1; ++y)
			Div2(sum, 0, e_x + 1, y, M - 1, visit);
		for (x = e_x + 1; x < M - 1; ++x)
			Div2(sum, 0, e_x + 1, N - 1, x, visit);
	}
	else if (e_x == M - 1 && e_y < N - 1) {
		for (x = 0; x < M - 1; ++x)
			Div2(sum, e_y + 1, 0, N - 1, x, visit);
		for (y = e_y + 1; y < N - 1; ++y)
			Div2(sum, e_y + 1, 0, y, M - 1, visit);
	}
	else {
		Div2(sum, 0, e_x + 1, e_y, M - 1, visit);
		Div2(sum, e_y + 1, 0, N - 1, e_x, visit);
	}
}

void Div() {
	int y = 0, x = 0;
	for (y = 0; y < N; ++y) {
		for (x = 0; x < M; ++x) {
			vector<vector<bool>>visit(N, vector<bool>(M, false));
			Div1(0, 0, y, x, visit);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	value = vector<vector<int>>(N, vector<int>(M, 0));

	int y = 0, x = 0;
	for (y = 0; y < N; ++y) {
		string num = "";
		cin >> num;
		for (x = 0; x < M; ++x) {
			value[y][x] = num[x] - '0';
		}
	}

	Div();

	cout << answer;
}