boj 1915 : 가장 큰 정사각형

boj 1915 : 가장 큰 정사각형

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

2가지 방법으로 풀었다.

첫번째 방법은 sum을 이용하여 해결하는 것.

sum[i][j]를 sum{ a[u][v] } (u는 1~i까지, v는 1~j까지)

sum[i][j] - sum[i-k+1][j] - sum[i][j-k+1] + sum[i-k+1][j-k+1] == k*k 일때 한변의 길이가 k인 정사각형이다. 아래의 사진을 보면 참고가 될지도 모르겠다.

하지만 위의 방법은 아슬아슬하게 시간초과를 면한다. 시간복잡도는 n*m*min(n,m)이다.

두번째 풀이법은 다른사람들의 코드를 보고 나서야 떠올릴 수 있었는데, c[i][j]를 i,j를 오른쪽 아래로 둘 때의 가장 큰 정사각형이라고 생각하자.

그러면,

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

위와같은 식이 나온다.

물론 i,j좌표가 1이 아닐 땐 c[i][j]는 0이다.

위의 두 번째 방법은 시간복잡도는 n*m이다.