boj 1915: 가장 큰 정사각형

1 ≤ n, m ≤ 1,000 이므로 브루트포스로 다 구해본다면 O(N^2M^2)로 시간 제한에 걸릴 것이다.

array를 무조건 한 번은 봐야하기 때문에 O(NM) * ???가 2초 안에 실행 되어야 한다.

 

DP로 풀어볼 수 있는 방법을 생각해 보자

dp[i][j]: (i,j)를 오른쪽 아래로 포함한 가장 크게 만들 수 있는 정사각형의 한 변 길이로 잡고, mat[i][j]==1일때 dp를 업데이트 한다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int row = in.nextInt();
		int col = in.nextInt();
		int mat[][] = new int[row][col];
		int dp[][] = new int[row][col];
		int maxLength = 0;

		for (int i = 0; i < row; i++) {
			String rowInput = in.next();
			int j = 0;
			for (char ch : rowInput.toCharArray()) {
				mat[i][j] = ch - '0';
				dp[i][j] = ch - '0';
				maxLength = ch - '0' > 0 ? 1 : 0;
				j++;
			}
		}

		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				if (mat[i][j] != 0) {
					dp[i][j] = findMinValueBetweenThree(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
					maxLength = Math.max(maxLength, dp[i][j]);
				}
			}
		}
		System.out.println(maxLength * maxLength);
	}

	public static int findMinValueBetweenThree(int a, int b, int c) {
		return Math.min(a, Math.min(b, c));
	}
}