[ BOJ ][JAVA][1451] 직사각형으로 나누기

www.acmicpc.net/problem/1451

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2266	811	618	37.073%

문제

세준이는 NM크기로 직사각형에 수를 NM개 써놓았다.

세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다.

어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다.

출력

세 개의 작은 직사각형의 합의 곱의 최댓값을 출력한다.

예제 입력 1

1 8
11911103

예제 출력 1

108

예제 입력 2

3 3
123
456
789

예제 출력 2

3264

예제 입력 3

3 1
7
9
3

예제 출력 3

189

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p1451 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] rectangle = new int[n][m];

        for(int i = 0; i < n; i++) {
            char[] temp = br.readLine().toCharArray();

            for(int j = 0; j < m; j++) {
                rectangle[i][j] = temp[j] - '0';
            }
        }

        long max = 0;

        for(int i = 1; i < n; i++) {
            long a = getRectangleSum(0, i, 0, m, rectangle);

            max = getMaxVertical(a, rectangle, max, i, n, 0, m);    
            max = getMaxHorizontal(a, rectangle, max, i, n, 0, m);
        }

        for(int i = n - 1; i > 0; i--) {
            long a = getRectangleSum(i, n, 0, m, rectangle);

            max = getMaxVertical(a, rectangle, max, 0, i, 0, m);        
        }

        for(int i = 1; i < m; i++) {
            long a = getRectangleSum(0, n, 0, i, rectangle);

            max = getMaxHorizontal(a, rectangle, max, 0, n, i, m);
            max = getMaxVertical(a, rectangle, max, 0, n, i, m);        
        }

        for(int i = m - 1; i > 0; i--) {
            long a = getRectangleSum(0, n, i, m, rectangle);

            max = getMaxHorizontal(a, rectangle, max, 0, n, 0, i);
        }

        System.out.println(max);
    }

    private static long getMaxHorizontal(long a, int[][] rectangle, long max, int sI, int eI, int sJ, int eJ) {

        for(int j = sI + 1; j < eI; j++) {
            long b = getRectangleSum(sI, j, sJ, eJ, rectangle);
            long c = getRectangleSum(j, eI, sJ, eJ, rectangle);

            long tmp = a * b * c;

            if(max < tmp) {
                max = tmp;
            }
        }

        return max;
    }

    private static long getMaxVertical(long a, int[][] rectangle, long max, int sI, int eI, int sJ, int eJ) {

        for(int j = sJ + 1; j < eJ; j++) {
            long b = getRectangleSum(sI, eI, sJ, j, rectangle);
            long c = getRectangleSum(sI, eI, j, eJ, rectangle);

            long tmp = a * b * c;

            if(max < tmp) {
                max = tmp;
            }
        }

        return max;
    }

    private static long getRectangleSum(int sI, int eI, int sJ, int eJ, int[][] rectangle) {
        long sum = 0;

        for(int i = sI; i < eI; i++) {
            for(int j = sJ; j < eJ; j++) {
                sum += rectangle[i][j];
            }
        }

        return sum;
    }
}