[BOJ] 1915. 가장 큰 정사각형

https://www.acmicpc.net/problem/1915 접근 방법 정사각형이 되는 경우를 생각해보았다. 현재 꼭짓점(x,y)에서 (x-1,y) (x,y-1) (x-1,y-1)이 모두 true라면 정사각형이다. 처음에는 재귀적으로 호출을 해서 정사각형을 체크하려 해주었음 당연히 시간 초과... 어떻게 하면 체크 한 것을 가지고 있으면서 정사각형이 최대가 되는지에 대한 생각... index는 11000, 11000이 모두 고정적이다. → 메모지에이션을 쓰면 되지 않을까? 동적프로그램을 생각해보았다. 위, 왼쪽, 왼쪽위 대각선이 모두 1일 경우 위, 왼쪽, 왼쪽위 대각선의 최소값에 +1을 더한값이 가장 큰 정사각형이 된다. 위, 왼쪽, 왼쪽위 대각선이 1일 경우 cache[i][k] = max( c..

2020.07.12