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

문제 설명

• https://www.acmicpc.net/problem/1451
• 주어진 직사각형을 3개의 직사각형으로 나누었을 때 조건을 만족하는 최대값을 구하는 문제입니다.
  각 직사각형 내부 숫자의 합을 t라고 할 때 나눈 직사각형 각각은 t1,t2,t3의 값을 가집니다.
  이 때 t1*t2*t3의 최대값을 찾아야 합니다.

접근법

• 잘린 직사각형의 합을 매번 구하는것보다 누적합을 이용해 구하는 게 더 빠릅니다.

  • 하나의 직사각형을 3등분 하는 방법은 ㅏ ,ㅓ, ㅗ, ㅜ, ||, = 입니다.
  • ㅏ ,ㅓ, ㅗ, ㅜ는 접점을 활용해 NxM배열에서 구할 수 있습니다.
  • ||와 =는 Combination을 활용해 구했습니다.

• N,M<=50이고 한 칸에 최대 9까지 적을 수 있기 때문에 최대 2500칸이 9로 채워질 수 있습니다. 이 경우 833,833,844개의 칸을 각각 가지고 이들의 내부 합은 7497, 7497, 7506이고 이걸로 답을 구하면 int의 범위를 초과합니다. long을 사용해야 합니다.

정답

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

public class Main {
	static long maxVal = Integer.MIN_VALUE;
	static int N,M;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int[][] board = new int[N][M];
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				board[i][j] = s.charAt(j)-'0';
			}			
		}
        // 누적합 구하기
		long[][] cumSum = new long[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(i == 0 && j == 0) {
					cumSum[i][j] = board[i][j];
				} else if (i == 0) {
					cumSum[i][j] = cumSum[i][j-1] + board[i][j];
				} else if (j == 0) {
					cumSum[i][j] = cumSum[i-1][j] + board[i][j];					
				} else {
					cumSum[i][j] = cumSum[i-1][j] + cumSum[i][j-1] - cumSum[i-1][j-1] + board[i][j];
				}
			}
		}
		
		Comb(0,0,M-1,new int[2],new boolean[M-1],cumSum, true); // || 모양
		Comb(0,0,N-1,new int[2],new boolean[N-1],cumSum, false); // = 모양
		
		for (int i = 0; i < N-1; i++) {
			for (int j = 0; j < M-1; j++) {
				long square1 = cumSum[i][j];
				long square2 = cumSum[i][M-1] - square1;
				long square3 = cumSum[N-1][j] - square1;
				long square4 = cumSum[N-1][M-1] - square3-square2-square1;
				maxVal = Math.max(maxVal, (square1+square2)*square3*square4); // ㅜ 모양
				maxVal = Math.max(maxVal, (square1+square3)*square2*square4); // ㅏ 모양
				maxVal = Math.max(maxVal, (square2+square4)*square1*square3); // ㅓ 모양
				maxVal = Math.max(maxVal, (square3+square4)*square1*square2); // ㅗ 모양
			}
		}			
		
		
		System.out.println(maxVal);
		
		
//		for (int i = 0; i < cumSum.length; i++) {
//			System.out.println(Arrays.toString(cumSum[i]));
//		}
		
		
	}
    // || 또는 = 모양에서 자를 두 곳을 구하는 조합
	public static void Comb(int depth,int start, int numLength,int[] answer, boolean[] v, long[][] cumSum, boolean isRow) {
		if(depth == 2) {
			int leftIdx = answer[0];
			int rightIdx = answer[1];
			if(isRow) {
				long square1 = cumSum[N-1][leftIdx];
				long square2 = cumSum[N-1][rightIdx] - cumSum[N-1][leftIdx];
				long square3 = cumSum[N-1][numLength] - cumSum[N-1][rightIdx];
				maxVal = Math.max(maxVal, square1 * square2 * square3);
			}else {
				long square1 = cumSum[leftIdx][M-1];
				long square2 = cumSum[rightIdx][M-1] - cumSum[leftIdx][M-1];
				long square3 = cumSum[numLength][M-1] - cumSum[rightIdx][M-1];
				maxVal = Math.max(maxVal, square1 * square2 * square3);				
			}
			return;
		}
		
		for (int i = start; i < numLength; i++) {
			if(v[i]) continue;
			answer[depth] = i;
			Comb(depth+1,i+1,numLength,answer,v, cumSum, isRow);
			v[i] = false;
		}
	}
}