[java 백준] 골드 5/1451번 직사각형으로 나누기

 

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

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

 

 

import java.io.IOException;
import java.util.Scanner;
 
public class Main {
 
    public static int n, m;
    public static int[][] arr;
 
    public static long sum(int ax, int ay, int bx, int by) {
        int cnt = 0;
 
        for (int i = ax; i <= bx; i++) {
            for (int j = ay; j <= by; j++) {
                cnt += arr[i][j];
            }
        }
        return cnt;
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n + 1][m + 1];
 
        for (int i = 0; i < n; i++) {
 
            String s = sc.next();
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
 
        }
        // 직사각형 나누는 방법 6가지
 
        // case 1
        // 꼭짓점,끝과 끝을 sum에 넣어주는 거
        long ans = 0;
 
        for (int i = 0; i < m - 2; i++) {// 축1
            for (int j = i + 1; j < m - 1; j++) {// 축2
                long sum1 = sum(0, 0, n - 1, i);
                long sum2 = sum(0, i + 1, n - 1, j);// i+1이 아니라 j 끝과 끝 생각
                long sum3 = sum(0, j + 1, n - 1, m - 1);
                if (ans < sum1 * sum2 * sum3) {
                    ans = sum1 * sum2 * sum3;
                }
 
            }
        }
 
        // case 2
 
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                long sum1 = sum(0, 0, i, m - 1);
                long sum2 = sum(i + 1, 0, j, m - 1);
                long sum3 = sum(j + 1, 0, n - 1, m - 1);
                if (ans < sum1 * sum2 * sum3) {
                    ans = sum1 * sum2 * sum3;
                }
            }
        }
 
        // case 3
        for (int i = 0; i < n - 1; i++) {// 행을 가르는 축
            for (int j = 0; j < m - 1; j++) {// 열을 가르는 축
                long sum1 = sum(0, 0, i, m - 1);
                long sum2 = sum(i + 1, 0, n - 1, j);
                long sum3 = sum(i + 1, j + 1, n - 1, m - 1);
                if (ans < sum1 * sum2 * sum3) {
                    ans = sum1 * sum2 * sum3;
                }
            }
        }
 
        // case 4
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                long sum1 = sum(0, 0, j, i);
                long sum2 = sum(0, i + 1, j, m - 1);
                long sum3 = sum(j + 1, 0, n - 1, m - 1);
                if (ans < sum1 * sum2 * sum3) {
                    ans = sum1 * sum2 * sum3;
                }
            }
        }
 
        // case 5
        for (int i = 0; i < m - 1; i++) {// 열을 가르는
            for (int j = 0; j < n - 1; j++) {
                long sum1 = sum(0, 0, n - 1, i);
                long sum2 = sum(0, i + 1, j, m - 1);
                long sum3 = sum(j + 1, i + 1, n - 1, m - 1);
                if (ans < sum1 * sum2 * sum3) {
                    ans = sum1 * sum2 * sum3;
                }
 
            }
 
        }
 
        // case 6
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                long sum1 = sum(0, 0, j, i);
                long sum2 = sum(j + 1, 0, n - 1, i);
                long sum3 = sum(0, i + 1, n - 1, m - 1);
                if (ans < sum1 * sum2 * sum3) {
                    ans = sum1 * sum2 * sum3;
                }
            }
        }
 
        System.out.println(ans);
 
    }
}

근데 문제는 이걸 어떻게 나눠주느냐에 있었다. 사실 너무 어려워서 다른 사람의 sum메서드 코드를 보았다. 

우선 구획한 직사각형을 더해주는 sum 메서드를 보자. 

 

 public static long sum(int ax, int ay, int bx, int by) {
        int cnt = 0;
 
        for (int i = ax; i <= bx; i++) {
            for (int j = ay; j <= by; j++) {
                cnt += arr[i][j];
            }
        }
        return cnt;
    }

 

 

직사각형이 시작하는 부분부터 끝나는 부분 즉 끝과 끝의 행과 열의 index를 받아서 더해주는 방법을 생각해보았다.

결국에 직사각형의 꼭짓점들만 받아올 수 있게 코드를 짜면 되겠다는 생각이 들었다.

 

 

case 1) 

얘의 경우 열을 가르는 축 2개만 필요하다. 두개의 축을 각각 i,j라 둘건데, i는 m-2 전까지 돌 수 있고 (적어도 2칸 남겨야함),j는 m-1 전까지 돌 수 있다.(적어도 뒤에 한칸 남겨야함)

 

 

sum함수에는 (시작점 행,시작점 열,끝점 행,끝점 열)을 넣어주면 된다.

 

 

 

case2)

 

그렇다면 행을 가르는 축을 i로 두고 열을 가르는 축을 j로 두자.

위와 같은 경우를 살펴볼 것이다.

 

이 모양도 위에랑 똑같이 행을 가르는걸 i축, 열을 가르는걸 j축으로 두면 된다.

 

아까 case1이랑 달라지는건 i는 m-2가 아니라 m-1 전까지 잘릴 수 있다. 왜냐면 얘는 2등분만 하면 되기 때문에 뒤에 한부분만 남기면 되기 때문이다. j도 m-1 전까지 자를 수 있다.

 

이해하면 그 다음부턴 코드가 술술 써지는데 처음에 기준잡는게 너무 어렵다....ㅜ

참고 사이트

https://dbstndi6316.tistory.com/116

[백준문제풀이] 1451 직사각형으로 나누기

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

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