백준 1915 가장 큰 정사각형

백준 Slack에서 고수분들이 말씀해주신 풀이를 적어보려 한다.

이 문제는 dp로 풀 수 있다.
주어진 배열에서 1로 된 가장 큰 정사각형의 크기를 구해야 하는데,
(r, c)를 가장 위, 왼쪽으로 해서 만들 수 있는 최대 정사각형과, (r+1, c)와 (r, c+1) 각각을 가장 위, 왼쪽으로 해서 만들 수 있는 최대 정사각형을 생각해보면,
d[r][c] = (r, c)를 가장 위의 가장 왼쪽으로 하는 가장 큰 정사각형의 한 변의 길이
라고 할 때,
d[r][c] = min(d[r+1][c], d[r][c+1]) + 1 이라고 볼 수 있을 것 같다.
하지만 d[r+1][c]와 d[r][c+1]이 같은 경우, 가장 오른쪽 아래 부분도 추가로 확인해봐야 한다. 가장 오른쪽 아래 부분이 0이면 d[r][c] = min(d[r+1][c], d[r][c+1]) 이 되는 것이고, 1이면 min(d[r+1][c], d[r][c+1]) + 1이 될 것이다.

시간복잡도는 O(N^2)정도가 나올 것 같다.