[알고리즘] Java / 백준 / 직사각형으로 나누기 / 1451

[알고리즘] Java / 백준 / 직사각형으로 나누기 / 1451

문제

문제 링크

접근 방식

가장 중요한 개념은 직사각형을 단 3개로만 나눈다는 것 이라 생각한다

1. 가로 혹은 세로로 나눌 모든 경우의 수를 생각한다 (가로는 N-1개, 세로는 M-1개로 나눌 수 있다)
2. 나눈 후 두 직사각형에 대해 자르지 않을 직사각형 하나를 선택한다 (경우의 수 = 2)
3. 자를 직사각형에 대해 가로 혹은 세로로 나눌 모든 경우의 수를 생각한다 (가로는 남은 직사각형의 행 -1, 세로 또한 남은 직사각형의 열 -1)
4. 각각의 경우의 수에 대해 세 직사각형 안에 들어있는 수를 누적합 dp 를 통해 O(1)로 계산한 후 곱하여 최댓값을 구한다

누적 합

	// 2차원 배열의 각각 위치는 이전 열 혹은 이전 행의 모든 값을 더한 값
	dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]  

특정 직사각형 안의 누적 합 구하기

    //x1, y1 부터 x2, y2까지의 직사각형 안의 수 합
    value = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

코드

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

public class Main_1451 {

	public static void main(String[] args) throws IOException{
		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());
		
		long[][] map = new long[N+1][M+1];
		
		for(int i=1;i<=N;i++) {
			String line = br.readLine();
			for(int j=1;j<=M;j++) {
				map[i][j] = map[i][j-1] + map[i-1][j] - map[i-1][j-1] + (line.charAt(j-1) -'0');
			}
		}
		
		long max = 0;
		for(int i=1; i< N;i++) {
			long basedown = map[N][M] - map[i][M];
			for(int j=1;j<M;j++) {
				long left = map[i][j];
				long right = map[i][M] - map[i][j];
				
				long mul = basedown * left * right;
				if(max < mul) max = mul; 	
			}
			
			for(int j=1;j<i;j++) {
				long up = map[j][M];
				long mid = map[i][M] - map[j][M];
				
				long mul = basedown * up * mid;
				if(max < mul) max = mul; 	
			}
			
			
			long baseup = map[i][M];
			
			for(int j=1;j<M;j++) {
				long left = map[N][j] - map[i][j];
				long right = map[N][M] - map[N][j] - map[i][M] + map[i][j];
				
				long mul = baseup * left * right;
				if(max < mul) max = mul;
			}
			
			for(int j=i+1;j<N;j++) {
				long mid = map[j][M] - map[i][M];
				long down = map[N][M] - map[j][M];
				
				long mul = baseup * mid * down;
				if(max < mul) max = mul;
			}
			
		}
		
		
		
		for(int j=1; j< M;j++) {
			long baseright = map[N][M] - map[N][j];
			for(int i=1;i<N;i++) {
				long up = map[i][j];
				long down = map[N][j] - map[i][j];
				
				long mul = baseright * up * down;
				if(max < mul) max = mul; 	
			}
			
			for(int i=1;i<j;i++) {
				long left = map[N][i];
				long mid = map[N][j] - map[N][i];
				
				long mul = baseright * left * mid;
				if(max < mul) max = mul; 	
			}
			
			
			long baseleft = map[N][j];
			
			for(int i=1;i<N;i++) {
				long up = map[i][M] - map[i][j];
				long down = map[N][M] - map[N][j] - map[i][M] + map[i][j];
				
				long mul = baseleft * up * down;
				if(max < mul) max = mul;
			}
			
			for(int i=j+1;i<M;i++) {
				long mid = map[N][i] - map[N][j];
				long right = map[N][M] - map[N][i];
				
				long mul = baseleft * mid * right;
				if(max < mul) max = mul;
			}
			
		}
		
		System.out.println(max);
	}

}