[백준] 1451번 자바 직사각형으로 나누기

문제 출처 

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

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

 

 

접근 방식 및 풀이

참고 : Baekjoon Online Judge 1451번 풀이

 

0. 문제 요약 

- 직사각형의 크기 : N * M

- 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누는 문제 

- 모든칸은 하나의 직사각형에 포함되어야한다.(남는 칸이 없어야한다.)

- 각 직사각형에 포함되어 있는 숫자의 합을 구한다음 합의 곱을 최대로 만드는 문제

 

1. 직사각형을 나누는 방법 6가지

 

 

총 6가지 밖에 없기때문에 직접 만들어서 더해 가는것이 해결방법~ ㅠ

 

2. 경우의 수 

 

• 세로로 나눌 때 가능한 경우의 수 (①) : N^2 개
• 가로로 나눌 때 가능한 경우의 수 (②) : M^2 개
• 나머지 4가지 방법으로 나눌 때 경우의 수(③, ④, ⑤, ⑥) : 각각 N*M개

 

3. 직사각형의 합을 효율적으로 구하는 방법

1) (1,1) ~ (i,j)까지의 합구하기

Sum[i][j]
= (1,1) ~ (i,j)까지의 합구하기
= Sum[i-1][j]+Sum[i][j-1] -Sum[i-1][j-1] +A[i][j] 

 

2) (a,b) ~(c,b) 합 구하기 

Sum[c][d] - Sum[c][b-1] - Sum[a-1][d] + Sum[a-1][b-1]

 

 

4. 처음에 구해 놓은 6가지 케이스를 직사각형 구하는 방법 적용

1) 케이스 ①번

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);
                if(ans < r1*r2*r3){
                    ans = r1*r2*r3;
                }
            }
       }

 

2) 케이스 ②번

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);
                if(ans < r1*r2*r3){
                    ans = r1*r2*r3;
                }
            }
        }

 

3) 케이스 ③ 번

for (int i=1; i<=N-1; i++) {
    for (int j=1; j<=M-1; j++) {
        long r1 = sum(1,1,N,j);
        long r2 = sum(1,j+1,i,M);
        long r3 = sum(i+1,j+1,N,M);
        if (ans < r1*r2*r3) {
            ans = r1*r2*r3;
        }
    }
}

 

4) 케이스 ④ 번

for (int i=1; i<=N-1; i++) {
    for (int j=1; j<=M-1; j++) {
        r1 = sum(1,1,i,j);                
        r2 = sum(i+1,1,N,j);
        r3 = sum(1,j+1,N,M);
        if (ans < r1*r2*r3) {
            ans = r1*r2*r3;
        }    
    }
}

 

 

5) 케이스 ⑤ 번

 

1 2 3 4 5 6 7 8 9 10

for (int i=1; i<=N-1; i++) {     for (int j=1; j<=M-1; j++) {        r1 = sum(1,1,i,M);                        r2 = sum(i+1,1,N,j);        r3 = sum(i+1,j+1,N,M);         if (ans < r1*r2*r3) {             ans = r1*r2*r3;         }         } }

 

6) 케이스 ⑥ 번

1 2 3 4 5 6 7 8 9 10

for (int i=1; i<=N-1; i++) {     for (int j=1; j<=M-1; j++) {         r1 = sum(1,1,i,j);                        r2 = sum(1,j+1,i,M);        r3 = sum(i+1,1,N,M);         if (ans < r1*r2*r3) {             ans = r1*r2*r3;         }         } }

 

 

소스 코드 

import java.util.Scanner;
 
public class Main {
    static int N, M;
    static int[][] map ;
    static long[][] sum ;
    static long ans;
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine();
 
        map =new int[N+1][M+1];
 
        // 거리계산시 나올 수 있는 최댓값 넣어두기
        for (int i = 1; i <= N; i++) {
            String input = " "+ sc.nextLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = input.charAt(j) -'0';
            }
        }
 
 
        sum = new long[N+1][M+1];
        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) map[i][j];
            }
        }
 
 
        ans=  0;
        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);
                if(ans < r1*r2*r3){
                    ans = r1*r2*r3;
                }
            }
        }
 
        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);
                if(ans < r1*r2*r3){
                    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,N,j);
                long r2 = sum(1,j+1,i,M);
                long r3 = sum(i+1,j+1,N,M);
                if (ans < r1*r2*r3) {
                    ans = r1*r2*r3;
                }
                r1 = sum(1,1,i,j);
                r2 = sum(i+1,1,N,j);
                r3 = sum(1,j+1,N,M);
                if (ans < r1*r2*r3) {
                    ans = r1*r2*r3;
                }
                r1 = sum(1,1,i,M);
                r2 = sum(i+1,1,N,j);
                r3 = sum(i+1,j+1,N,M);
                if (ans < r1*r2*r3) {
                    ans = r1*r2*r3;
                }
                r1 = sum(1,1,i,j);
                r2 = sum(1,j+1,i,M);
                r3 = sum(i+1,1,N,M);
                if (ans < r1*r2*r3) {
                    ans = r1*r2*r3;
                }
            }
        }
        System.out.println(ans);
    }
 
    private 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] ;
    }
 
}

 

 

결과