[알고리즘] 직사각형으로 나누기 (with JAVA)

 

생각의 흐름

각 직사각형들의 숫자 합을 곱한 값이 가장 크게 만들려면 사용해야 하는 알고리즘이 따로 있을까?

• ⇒ 다 해보고 큰 값을 출력해야 한다고 생각함(브루트포스)

• • 구분할 인덱스 두개를 선택→ 그 내부에 있는 수들은 더해 저장→ 곱한 값 저장
    • X → 행이 여러개일 땐 인덱스 하나로 나뉘어지지가 않음 ⇒ 직사각형 구분을 어떻게 할 수 있을까? ⇒ (블로그 참고) 일일히 6가지 경우를 구한다..!!

각각 구해야 하는 6가지 경우에 대한 그림이다.

 

⚠️오답 코드

public class P1451_직사각형으로나누기 {
    static long max=0;
    static int [][] list;
    static int n,m;
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        list = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            String line = br.readLine();
            for (int j=1;j<=m;j++) {
                list[i][j] = line.charAt(j-1)-'0';
            }
        }
        System.out.println(solve());

    }
    static int sum(int a, int b, int c, int d) {
        int tempSum=0;
        for (int i = a; i <= c; i++) {
            for (int j = b; j <= d; j++) {
                tempSum+=list[i][j];
            }
        }
        return tempSum;
    }
    static long solve(){
        // ㅣ*3 모양

        for (int i = 1; i <= m-2; i++) {
            for (int j = i+1; j <= m-1; j++) {
                int r1= sum(1,1,n,i);
                int r2= sum(1,i+1,n,j);
                int r3= sum(1,j+1,n,m);

                max=Math.max(max,r1*r2*r3);
            }
        }
        // ㅡ*3 모양

        for (int i = 1; i <= n - 2; i++) {
            for (int j = i + 1; j <= n - 1; j++) {
                int r1 = sum(1, 1, i, m);
                int r2 = sum(i + 1, 1, i, m);
                int r3 = sum(j + 1, 1, n, m);

                max=Math.max(max,r1*r2*r3);
            }
        }

        // ㅏ 모양
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int r1= sum(1,1,n,j);
                int r2= sum(1,j+1,i,m);
                int r3= sum(i+1,j+1,n,m);

                max=Math.max(max,r1*r2*r3);            }
        }
        // ㅓ 모양

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int r1= sum(1,1,i,j);
                int r2= sum(i+1,1,n,j);
                int r3= sum(1,j+1,n,m);

                max=Math.max(max,r1*r2*r3);            }
        }
        //ㅗ모양
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int r1= sum(1,1,i,j);
                int r2= sum(i+1,1,n,m);
                int r3= sum(1,j+1,i,m);

                max=Math.max(max,r1*r2*r3);            }
        }
        //ㅜ모양
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int r1= sum(1,1,i,m);
                int r2= sum(i+1,1,n,j);
                int r3= sum(i+1,j+1,n,m);

                max=Math.max(max,r1*r2*r3);            }
        }
        return max;
    }
}

• 테스트 코드는 돌아가는데 틀렸다고 뜬다..
• 누적합을 사용해야만 하는 것인가..?
• 블로그를 보면서 수정해보자

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

 

📋누적합 활용 점화식

prefixSum[r2][c2] - prefixSum[r2][c1-1] - prefixSum[r1-1][c2] + prefixSum[r1-1][c1-1]

---

정답 코드

public class P1451_직사각형으로나누기 {
    static long max=0;
    static int [][] list;
    static int n,m;
    static long[][] prefixSum;
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        list = new int[n+1][m+1];
        prefixSum = new long[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            String line = br.readLine();
            for (int j=1;j<=m;j++) {
                list[i][j] = line.charAt(j-1)-'0';
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                prefixSum[i][j] = list[i][j] + prefixSum[i][j-1] + prefixSum[i-1][j] - prefixSum[i-1][j-1];
            }
        }

        System.out.println(solve());

    }
    static long sum(int r1, int c1, int r2, int c2) {
                //누적합 사용
        return  prefixSum[r2][c2] - prefixSum[r2][c1-1] - prefixSum[r1-1][c2] + prefixSum[r1-1][c1-1];

    }
    static long solve(){
        // ㅣ*3 모양

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

                max=Math.max(max,r1*r2*r3);
            }
        }
        // ㅡ*3 모양

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

                max=Math.max(max,r1*r2*r3);
            }
        }

        // ㅏ 모양
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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);

                max=Math.max(max,r1*r2*r3);            }
        }
        // ㅓ 모양

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                long r1= sum(1,1,i,j);
                long r2= sum(i+1,1,n,j);
                long r3= sum(1,j+1,n,m);

                max=Math.max(max,r1*r2*r3);            }
        }
        //ㅗ모양
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                long r1= sum(1,1,i,j);
                long r2= sum(i+1,1,n,m);
                long r3= sum(1,j+1,i,m);

                max=Math.max(max,r1*r2*r3);            }
        }
        //ㅜ모양
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                long r1= sum(1,1,i,m);
                long r2= sum(i+1,1,n,j);
                long r3= sum(i+1,j+1,n,m);

                max=Math.max(max,r1*r2*r3);
            }
        }
        return max;
    }
}