[BaekJoon] 1451 직사각형으로 나누기 (Java)

1.  문제 링크

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

2.  문제

요약

• N M 크기의 직사각형에 수를 N M개 써놓았습니다.
• 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 하는데, 각 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각 작은 직사각형은 적어도 하나의 숫자를 포함해야 합니다.
• 어떤 작은 직사각형의 합은 그 속에 있는 수의 합을 뜻합니다.
• 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나눌 때, 각각의 작은 직사각형의 합의 곱의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 50보다 작거나 같은 자연수인 직사각형의 세로 크기 N과 가로 크기 M이 주어지고 두 번째 줄부터 N개의 줄에는 한 자리의 숫자인 직사각형에 들어가는 수가 M개 주어집니다. 직사각형엔 적어도 3개의 수가 있습니다.
• 출력: 첫 번째 줄에 세 개의 작은 직사각형의 합의 곱의 최댓값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public long getMaxMultiply(int[][] nums, int row, int col) {
		long result = 0L;
		long[][] sum = new long[row + 1][col + 1];
		for(int i = 1; i <= row; i++) {
			for(int j = 1; j <= col; j++) {
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (long)nums[i][j];
			}
		}
		
		for(int i = 1; i <= col - 2; i++) {
			for(int j = i + 1; j <= col - 1; j++) {
				long rectangle1 = sum[row][i] - sum[row][0] - sum[0][i] + sum[0][0];
				long rectangle2 = sum[row][j] - sum[row][i] - sum[0][j] + sum[0][i];
				long rectangle3 = sum[row][col] - sum[row][j] - sum[0][col] + sum[0][j];
				if(result < rectangle1 * rectangle2 * rectangle3) {
					result = rectangle1 * rectangle2 * rectangle3;
				}
			}
		}
		
		for(int i = 1; i <= row - 2; i++) {
			for(int j = i + 1; j <= row - 1; j++) {
				long rectangle1 = sum[i][col] - sum[i][0] - sum[0][col] + sum[0][0];
				long rectangle2 = sum[j][col] - sum[j][0] - sum[i][col] + sum[i][0];
				long rectangle3 = sum[row][col] - sum[row][0] - sum[j][col] + sum[j][0];
				if(result < rectangle1 * rectangle2 * rectangle3) {
					result = rectangle1 * rectangle2 * rectangle3;
				}
			}
		}
		
		for(int i = 1; i <= row - 1; i++) {
			for(int j = 1; j <= col - 1; j++) {
				long rectangle1 = sum[row][j] - sum[row][0] - sum[0][j] + sum[0][0];
				long rectangle2 = sum[i][col] - sum[i][j] - sum[0][col] + sum[0][j];
				long rectangle3 = sum[row][col] - sum[row][j] - sum[i][col] + sum[i][j];
				if(result < rectangle1 * rectangle2 * rectangle3) {
					result = rectangle1 * rectangle2 * rectangle3;
				}
				
				rectangle1 = sum[i][j] - sum[i][0] - sum[0][j] + sum[0][0];
				rectangle2 = sum[row][j] - sum[row][0] - sum[i][j] + sum[i][0];
				rectangle3 = sum[row][col] - sum[row][j] - sum[0][col] + sum[0][j];
				if(result < rectangle1 * rectangle2 * rectangle3) {
					result = rectangle1 * rectangle2 * rectangle3;
				}
				
				rectangle1 = sum[i][col] - sum[i][0] - sum[0][col] + sum[0][0];
				rectangle2 = sum[row][j] - sum[row][0] - sum[i][j] + sum[i][0];
				rectangle3 = sum[row][col] - sum[row][j] - sum[i][col] + sum[i][j];
				if(result < rectangle1 * rectangle2 * rectangle3) {
					result = rectangle1 * rectangle2 * rectangle3;
				}
				
				rectangle1 = sum[i][j] - sum[i][0] - sum[0][j] + sum[0][0];
				rectangle2 = sum[i][col] - sum[i][j] - sum[0][col] + sum[0][j];
				rectangle3 = sum[row][col] - sum[row][0] - sum[i][col] + sum[i][0];
				if(result < rectangle1 * rectangle2 * rectangle3) {
					result = rectangle1 * rectangle2 * rectangle3;
				}
			}
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int row = Integer.parseInt(input[0]);
		int col = Integer.parseInt(input[1]);
		int[][] nums = new int[row + 1][col + 1];
		for(int i = 1; i <= row; i++) {
			String str = br.readLine();
			for(int j = 1; j <= col; j++) {
				nums[i][j] = str.charAt(j - 1) - '0';
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxMultiply(nums, row, col) + "\n");
		bw.flush();
		bw.close();
	}
}