백준 1915. 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

 

진짜 금방 풀수 있었는데 아주 조금 엇나가서 시간이 걸려버렸다.

처음에 생각한건 d[i][j] = (i,j)를 가장 오른쪽 아래로 하는 정사각형의 한 변의 크기의 최댓값 

따라서 (i,j)를 기준으로 위, 왼쪽이 0이 넘는다면 즉 d[i-1][j], d[i][j-1] 중 작은 값을 len으로 하고, 

d[i-len][j-len] > 0 이면 d[i][j] = len + 1이라고 생각했는데 대각선 왼쪽 위 방향을 생각을 못했다.

 

결론적으로 d[i][j]는 위대로고, 점화식은 아래와 같다. 

d[i][j] = min(d[i-1][j-1], min(d[i-1][j], d[i][j-1]))+1;