[leetcode][1277] Count Square Submatrices with All Ones
문제 : https://leetcode.com/problems/count-square-submatrices-with-all-ones/ 1과 0으로 이루어진 N x M 배열이 주어지면 1로 이루어진 정사각형의 개수를 구하라. 행, 열 subsum을 구한 뒤 이를 이용하여 구했다. 입력배열이 위와 같으면 행, 열 부분합 배열은 각각 위와같이 만들어진다. (2,1) 한 칸이 정사각형인지 판단하는 방법은 행 부분합에서 (2, 1) - (1,1) 값과 열 부분합에서 (2,1) - (2,0) 값이 둘 다 1이어야 한다. 즉, (2,1) 값이 1인지 확인하기만 하면 된다. 그 다음 (2,1)을 정사각형의 왼쪽 모서리로 두고 사이즈가 2인 정사각형이 가능한지 판단해보자. 이전 단계에서 (2, 1)은 모두 1인 것을 판..
2020. 5. 23.
