1915 가장 큰 정사각형

n * m의 배열에 0,1 의 값이 있는데, 1의 값으로 채워져 있는 가장 큰 정사각형의 넓이를 구하는 문제이다.

이 문제는 DP로 해결이 가능한데, dp를 구성하는 방법은 다음과 같이 하면 된다.


(i = 0~m-1, j = 0~n-1)
dp[0][j] = 좌표값이 1이면 1, 아니면 0.
dp[i][0] = 좌표값이 1이면 1, 아니면 0.

i,j 좌표값이 1일 때,
dp[i][j] =  1+MIN(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])

이 때 나온 dp 값중에 최대값을 저장해서, 넓이를 출력하면 된다.

소스