[백준] 1451 직사각형으로 나누기 java

import java.io.*;
import java.util.*;

public class DivisionSquare {
    static BufferedReader br;
    static StringTokenizer st;
    static int N, M;
    static int[][] arr;
    static long[][] sum;
    static long ans = -1;

    public static void main(String[] args) throws IOException{
        input();
        solve();
        System.out.println(ans);
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N+1][M+1];
        sum = new long[N+1][M+1];
        for(int[] a : arr) {
            Arrays.fill(a, 0);
        }
        for(int i = 1; i <= N; i++) {
            String s = br.readLine();
            for(int j = 1; j <= M; j++) {
                arr[i][j] = s.charAt(j-1) - '0';
            }
        }
    }


    public static void solve() {
        //1. sum 구하기
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (long)arr[i][j];
            }
        }

        //2. 6개의 경우 별로 곱의 합 구하기

        //가로 3개
        for(int i = 1; i <= N-2; i++) {
            for(int j = i+1; j <= N-1; j++) {
                long r1 = sum(1, 1, i, M);
                long r2 = sum(i+1, 1, j, M);
                long r3 = sum(j+1, 1, N, M);
                ans = Math.max(ans, r1 * r2 * r3);
            }
        }

        //세로 3개
        for(int i = 1;  i <= M-2; i++) {
            for(int j = i+1; j <= M-1; j++) {
                long r1 = sum(1, 1, N, i);
                long r2 = sum(1, i+1, N, j);
                long r3 = sum(1, j+1, N, M);
                ans = Math.max(ans, r1 * r2 * r3);
            }
        }

        //ㅜ형
       for(int i = 1; i <= N-1; i++) {
           for(int j = 1; j <= M-1; j++) {
               long r1 = sum(1, 1, i, M);
               long r2 = sum(i+1, 1, N, j);
               long r3 = sum(i+1, j+1, N, M);

               ans = Math.max(ans, r1*r2*r3);
           }
       }
        //ㅗ형
       for(int i = N; i > 1; i--) {
           for(int j = 1; j <= M-1; j++) {
               long r1 = sum(i, 1, N, M);
               long r2 = sum(1, 1, i-1, j);
               long r3 = sum(1, j+1, i-1, M);

               ans = Math.max(ans, r1*r2*r3);
           }
       }

       //ㅏ형
        for(int i = 1; i <= M-1; i++) {
            for(int j = 1; j <= N-1; j++) {
                long r1 = sum(1, 1, N, i);
                long r2 = sum(1, i+1, j, M);
                long r3 = sum(j+1, i+1, N, M);

                ans = Math.max(ans, r1*r2*r3);
            }
        }

        //ㅓ형
        for(int i = M; i > 1; i--) {
            for(int j = 1; j <= N-1; j++) {
                long r1 = sum(1, i, N, M);
                long r2 = sum(1, 1, j, i-1);
                long r3 = sum(j+1, 1, N, i-1);

                ans = Math.max(ans, r1*r2*r3);
            }
        }
    }

    public static long sum(int x1, int y1, int x2, int y2) {
        return sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
    }
}

완전탐색 문제이고 조건 분기가 꽤 있는 문제이다. 나는 어떻게 풀어야할지 아이디어가 떠오르지 않아서 다른 분들의 코드를 보면서 풀었다. 관건은 모든 경우의 수를 적절히 알고 좌표의 위치를 틀리지 않고 모두 돌 수 있어야 한다.

 

우선 해야할 일은 크게 2가지다.

 

1. 각 좌표의 위치마다 sum 구해놓기

2. 6가지의 경우의 수에서 가질 수 있는 경우의 수 모두 구하기

 

1번은 알고리즘이 좀 더 효율성을 내기 위해서 미리 합을 구해놓는 것이다. 

만약 2번에서 경우의 수 마다 매번 2중 for문을 돌리면서 답을 구해야 한다면 꽤나 비효율적이다. 하지만 미리 구해 놓는다면 단 한번의 연산만으로 해당 위치의 sum값을 구할 수가 있다. 시간복잡도면에서 훌륭한 전략이다.

 

2번은 6가지의 경우로 나눠서 생각을 할 수가 있다.

 

1. 가로 3개

2. 세로 3개

3. 세로 1개, 가로 2개

4. 3번의 반대

5. 가로 1개, 세로 2개

6. 5번의 반대

 

이렇게 6개의 경우에서 또 직사각형의 크기마다 sum을 구해서 현재 최대값과 계속해서 비교한다.