kthng

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를 오른쪽 아래로 둘 때의 가장 큰 정사각형이라고 생각하자. 그러면..