[백준 - 1451][Gold 4][해설 X] - 직사각형으로 나누기 (JAVA)

문제 링크

---

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

 

 

문제

---

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

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

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

 

입력

---

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

 

출력

---

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

 

해결 코드

---

 

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

/*
	가능한 직사각형의 모습은 총 6가지이다.
    1. 가로 3개
    2. 세로 3개
    3. 왼쪽 1개 오른쪽 2개
    4. 왼쪽 2개 오른쪽 1개
    5. 위 1개 아래 2개
    6. 위 2개 아래 1개
    
    
	이를 모두 N^2으로 구하면 제한 시간 이내로 구할 수 있다.
*/

public class Main {
    static long max =0;
    static int[][] map;
    static int[][] preSum;

    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());

        map = new int[N + 1][M + 1];
        preSum = new int[N + 1][M + 1];
		
        //누적합 및 값 세팅
        for (int i = 0; i < N; i++) {
            String input = br.readLine();

            for (int j = 0; j < input.length(); j++) {
                map[i + 1][j + 1] = input.charAt(j) - '0';
                preSum[i + 1][j + 1] = preSum[i + 1][j] + preSum[i][j + 1] - preSum[i][j] + map[i + 1][j + 1];
            }
        }

        //세로 3개
        for (int col1 = 1; col1 <= M - 2; col1++) {
            for (int col2 = col1 + 1; col2 <= M - 1; col2++) {
                Rect rect1 = new Rect(1, 1, N, col1);
                Rect rect2 = new Rect(1, col1 + 1, N, col2);
                Rect rect3 = new Rect(1, col2 + 1, N, M);

                max = Math.max(max, getPreSum(rect1) * getPreSum(rect2) * getPreSum(rect3));
            }
        }

        //가로 3개
        for (int row1 = 1; row1 <= N - 2; row1++) {
            for (int row2 = row1 + 1; row2 <= N - 1; row2++) {
                Rect rect1 = new Rect(1, 1, row1, M);
                Rect rect2 = new Rect(row1 + 1, 1, row2, M);
                Rect rect3 = new Rect(row2 + 1, 1, N, M);

                max = Math.max(max, getPreSum(rect1) * getPreSum(rect2) * getPreSum(rect3));
            }
        }
        //왼1 오2
        for (int row = 1; row < N; row++) {
            for (int col = 1; col < M; col++) {
                //왼1 오2
                Rect rect1 = new Rect(1, 1, N, col);
                Rect rect2 = new Rect(row + 1, col + 1, N, M);
                Rect rect3 = new Rect(1, col + 1, row, M);

                max = Math.max(max, getPreSum(rect1) * getPreSum(rect2) * getPreSum(rect3));

                //왼2 오1
                rect1 = new Rect(1, 1, row, col);
                rect2 = new Rect(row + 1, 1, N, col);
                rect3 = new Rect(1, col + 1, N, M);

                max = Math.max(max, getPreSum(rect1) * getPreSum(rect2) * getPreSum(rect3));

                //위1 아2
                rect1 = new Rect(1, 1, row, M);
                rect2 = new Rect(row + 1, 1, N, col);
                rect3 = new Rect(row + 1, col + 1, N, M);

                max = Math.max(max, getPreSum(rect1) * getPreSum(rect2) * getPreSum(rect3));

                //위2 아1
                rect1 = new Rect(1, 1, row, col);
                rect2 = new Rect(1, col + 1, row, M);
                rect3 = new Rect(row + 1, 1, N, M);

                max = Math.max(max, getPreSum(rect1) * getPreSum(rect2) * getPreSum(rect3));
            }
        }

        System.out.println(max);
    }
	
    //2차원 배열의 누적합을 구해주는 메소드
    public static long getPreSum(Rect rect){
        return preSum[rect.rightBottomRow][rect.rightBottomCol]
                - preSum[rect.rightBottomRow][rect.leftTopCol-1]
                - preSum[rect.leftTopRow-1][rect.rightBottomCol]
                + preSum[rect.leftTopRow -1][rect.leftTopCol-1];
    }
}
class Rect{
    int leftTopRow;
    int leftTopCol;
    int rightBottomRow;
    int rightBottomCol;

    public Rect(int leftTopRow,int leftTopCol,int rightBottomRow,int rightBottomCol){
        this.leftTopRow = leftTopRow;
        this.leftTopCol = leftTopCol;
        this.rightBottomRow = rightBottomRow;
        this.rightBottomCol = rightBottomCol;
    }
}

 

 

실행 결과

---

 

 

팁

---

• N이 1000미만이면 구현부터 생각하자
• 규칙이 생각이 잘 나지 않으면 모든 경우의 수를 그려보자