[Problem Solving - Baekjoon] 1915 가장 큰 정사각형

[Baekjoon Online Judge] 1915 가장 큰 정사각형

문제

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

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

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

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

예제

• input

4 4
0100
0111
1110
0010

• output

4

분류

• 다이나믹 프로그래밍

풀이

문제 파악

• 1로 된 가장 큰 정사각형의 크기를 구하기
• (1,1) 이 1인 경우에 정사각형이 될 수 있음 (arr[i] [j] == 1)
• 점화식은 dp[i] [j] = math.min (dp[i-1] [j], dp[i] [j-1], dp[i-1] [j-1]) +1 와 같이 세울 수 있음

(0,0) 1	(1,0) 1
(0,1) 1	(1,1) 1

• dp

	0	1	2	3	4
0	0	0	0	0	0
1	0	0	1	0	0
2	0	0	1	1	1
3	0	1	1	2	0
4	0	0	0	1	0

구현

전체소스보기

• math.min 이 두가지의 숫자만 비교 가능해서 나누어서 비교

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

for (int i = 1; i < n+1; i++) {
    for (int j = 1; j < m+1 ; j++) {
        if (arr[i][j] == 1 ) {
            int min = Math.min(dp[i-1][j], dp[i][j-1]);
            dp[i][j] = Math.min(min, dp[i-1][j-1]) + 1;
        }
    }
}

---

references

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