[백준] 1451. 직사각형으로 나누기 - JAVA

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

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

---

와 이 문제 푸는데 거의 2시간 걸린듯,,,

왜이렇게 어렵지,,,

어렵다기보다 사각형 넓이 구하는 과정이 헷갈림

인덱스들 맞추는거,,,ㅠㅠ 

암튼 참고한 블로그 내용을 설명해보겠다

 

---

직사각형을 나누는 방법

• 3개의 직사각형으로 나눌 수 있는 경우의 수는 위의 6가지가 전부이다
• 그래서 그냥 다 구해보는 수 밖에 없다~

 

 

 

직사각형의 합을 구하는 방법

• 이걸로는 미리 sum 배열을 만들어둔다
• 해당 값에 저장될 수 있는 최댓값을 위의 방식을 통해 구해주는 것이다
• 아마 이 부분때문에 DP라고 할 수 있을 것 같다

 

• 이는 3개의 직사각형으로 나누고, 나눈 직사각형의 넓이를 구할 떄 사용하는 공식이다
• 난 이 부분에서 인덱스를 결정하는게 굉장히 헷갈렸따..

 

 

 

직사각형을 나누는 경우별 넓이 구하기

1) 케이스 1번

• r1 : 파란색
• r2 : 분홍색
• r3 : 초록색

 

 

2) 케이스 2번

• r1 : 파란색
• r2 : 분홍색
• r3 : 초록색

 

3) 케이스 3번

• r1 : 파란색
• r2 : 분홍색
• r3 : 초록색

 

4) 케이스 4번

• r1 : 분홍색
• r2 : 초록색
• r3 : 파란색

 

5) 케이스 5번

• r1 : 분홍색
• r2 : 파란색
• r3 : 초록색

 

6) 케이스 6번

• r1 : 분홍색
• r2 : 파란색
• r3 : 초록색

 

 

 

자바 코드)

import java.util.Scanner;

public class Main {
    static int n,m;
    static int[][] arr;
    static long[][] sum;

    public static void main(String[] args) {
        long answer = 0;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        scanner.nextLine();

        arr = new int[n+1][m+1];

        for(int i=1;i<=n;i++) {
            String str = " " + scanner.nextLine();
            for(int j=1;j<=m;j++) {
                arr[i][j] = str.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) arr[i][j];
            }
        }

        // case 1
        for(int i=1;i<=m-1;i++) {
            for(int j=i+1;j<=m-2;j++) {
                long r1 = area(1,1,n,i);
                long r2 = area(1,i+1,n,j);
                long r3 = area(1,j+1,n,m);
                if(answer<r1*r2*r3) {
                    answer = r1*r2*r3;
                }
            }
        }

        // case 2
        for(int i=1;i<=n-1;i++) {
            for(int j=i+1;j<=n-1;j++) {
                long r1 = area(1,1,i,m);
                long r2 = area(i+1,1,j,m);
                long r3 = area(j+1,1,n,m);
                if(answer<r1*r2*r3) {
                    answer = r1*r2*r3;
                }
            }
        }

        //case 3
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                long r1 = area(1,1,n,i);
                long r2 = area(1,i+1,j,m);
                long r3 = area(j+1,i+1,n,m);
                if(answer<r1*r2*r3) {
                    answer = r1*r2*r3;
                }
            }
        }

        //case 4
        for(int i=1;i<n;i++) {
            for(int j=1;j<m;j++) {
                long r1 = area(1,1,i,j);
                long r2 = area(i+1,1,n,j);
                long r3 = area(1,j+1,n,m);
                if(answer<r1*r2*r3) {
                    answer = r1*r2*r3;
                }
            }
        }

        //case 5
        for(int i=1;i<n;i++) {
            for(int j=1;j<m;j++) {
                long r1 = area(1,1,i,m);
                long r2 = area(i+1,1,n,j);
                long r3 = area(i+1,j+1,n,m);
                if(answer<r1*r2*r3) {
                    answer = r1*r2*r3;
                }
            }
        }

        //case 6
        for(int i=1;i<n;i++) {
            for(int j=1;j<m;j++) {
                long r1 = area(1,1,i,j);
                long r2 = area(1,j+1,i,m);
                long r3 = area(i+1,1,n,m);
                if(answer<r1*r2*r3) {
                    answer = r1*r2*r3;
                }
            }
        }

        System.out.println(answer);
    }

    private static long area(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];
    }
}

 

 

---

참고)

https://log-laboratory.tistory.com/128

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