c언어 1451번 직사각형으로 나누기 (백준)

#include <stdio.h>

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);
	long long a[51][51] = {};
	char s[51];

	for(int i=1; i<=n; i++) {
		char s[51];
		scanf("%s", s);
		for(int j=1; j<=m; j++)
		a[i][j] = s[j-1]-48 + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
	}
	
	long long ans = 0, tmp;
	//가로, 세로 3등분 
	for(int i=1; i<m-1; i++)
	for(int j=i+1; j<m; j++) {
		tmp = a[n][i] * (a[n][j]-a[n][i]) * (a[n][m]-a[n][j]); //가로 
		ans = (ans > tmp) ? ans : tmp;
	}
	
	for(int i=1; i<n-1; i++)
	for(int j=i+1; j<n; j++) {
		tmp = a[i][m] * (a[j][m]-a[i][m]) * (a[n][m]-a[j][m]); //세로 
		ans = (ans > tmp) ? ans : tmp;
	}
	
	
	//ㅗ, ㅜ, ㅓ, ㅏ 등분
	for(int i=1; i<n; i++)
	for(int j=1; j<m; j++) {
		tmp = a[i][j] * (a[i][m]-a[i][j]) * (a[n][m] - a[i][m]); //ㅗ
		ans = (ans > tmp) ? ans : tmp;
		tmp = a[i][m] * (a[n][j]-a[i][j]) * (a[n][m]-a[i][m]-a[n][j]+a[i][j]); //ㅜ 
		ans = (ans > tmp) ? ans : tmp;
		tmp = a[i][j] * (a[n][j]-a[i][j]) * (a[n][m] - a[n][j]); //ㅓ 
		ans = (ans > tmp) ? ans : tmp;
		tmp = a[n][j] * (a[i][m]-a[i][j]) * (a[n][m]-a[i][m]-a[n][j]+a[i][j]); //ㅏ 
		ans = (ans > tmp) ? ans : tmp;
	}	printf("%lld", ans);
}

풀이 : 여러 조건분기, 누적합

 

1. 누적 합을 이용하여, 입력 받은 숫자들을 배열에다가 누적 합의 형태로 저장해 둡니다.

2. 직사각형 3개로 나누는 방법은 총 6가지가 존재합니다.

 

가로로 3등분, 세로로 3등분 ㅏ ㅓ ㅗ ㅜ  이렇게 총 6개 입니다.

이 6개의 방법들로 나누면서 가장 큰 값을 찾아서 출력하면 됩니다.

 

총 6가지의 방식으로 직사각형 3개를 만들어 낼 수 있습니다.

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

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