JuSeok

1915번

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

문제 해결 순서

  1. dp 유형의 문제.
  2. 점화식을 최대한 빠르게 알아내기 위해선 무조건 반대로 생각하기.
  3. 메모이제이션 배열이 존재한다는 것을 잊지않기.
  4. 2, 3번에 따라서 배열 맨 마지막 부터 차근차근 생각해보자...
  5. 왼쪽에서 오른쪽으로, 위에서 아래로 배열을 탐색하기 때문에 마지막인 오른쪽 아래에 주목.
  6. 예를들어 2 * 2 정사각형에서 (1, 1)에 메모이제이션의 값을 넣기 위해선 (0, 0), (0, 1), (1, 0), (1, 1) 4 좌표의 값이 1이어야한다.
  7. 한 마디로 n m배열을 2 2배열로 여러번 나눠서 본다는 뜻.
  8. 6번의 예제 같은 경우 4좌표가 1이기 때문에 메모이제이션 (1, 1)에 다른 3좌표의 값 중 작은 값 +1 을 저장함
  9. 왜 1이 아니라 3좌표중 작은 값 +1을 저장할까? 만약 3 * 3이 전부 1일 경우 메모이제이션 (1, 1), (1, 2), (2, 1) 세 좌표는 1로 메모이제이션 된다. 이렇게 될 경우 (2, 2)는 1로 메모이제이션 된 값들에게 둘러싸인 형태가 된다. 즉 1, 1, 1중 작은 값 +1을 하게돼 (2, 2)에는 2가 메모이제이션 되는 것이다.
  10. dp 문제는 항상 풀땐 엄청 어렵지만 막상 점화식을 알게되면 그렇게 쉬울 수가 없다... 점화식을 빠르게 파악하자!
import java.io.*;
import java.util.Scanner;

class Main {
    static int n, m, ans;
    static String s;    
    static int[][] a = new int[1001][1001], d = new int[1001][1001];

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 0; i < n; i++) {
            s = in.next();
            for (int j = 0; j < m; j++) {
                a[i][j] = s.charAt(j) - 48;
                if (a[i][j] == 1) {
                    d[i][j] = 1;
                    ans = 1;
                }
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (a[i - 1][j] == 1 && a[i - 1][j - 1] == 1 && a[i][j - 1] == 1 && a[i][j] == 1)  {
                    d[i][j] = Math.min(d[i - 1][j], d[i - 1][j - 1]);
                    d[i][j] = Math.min(d[i][j], d[i][j - 1]) + 1;
                }
                ans = Math.max(d[i][j], ans);
            }
        }
        System.out.println(ans * ans);
        in.close();
    }
}

Tags