[99클럽] 코테 스터디 20일차 TIL - DP(1277. Count Square Submatrices with All Ones)

문제

1277. Count Square Submatrices with All Ones
      https://leetcode.com/problems/count-square-submatrices-with-all-ones/

풀이 방법

1. 행, 열 부분합 배열을 만든다.
2. 이중 for로 matrix의 모든 값을 정사각형의 모서리로 가정하고 탐색한다.
   • 이때 가능한 정사각형의 최대 크기를 구해서 크기가 1, 2, ... 최대 크기의 정사각형의 개수를 구한다.
3. 딴짓하다 까먹었다.

코드

class Solution {
    public int countSquares(int[][] matrix) {
        int row = matrix.length;
        int column = matrix[0].length;


        int[][] rowSum = new int[row + 1][column + 1];
        int[][] colSum = new int[row + 1][column + 1];

        // 행, 열 합 부분 합 배열 생성 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                rowSum[i + 1][j + 1] = rowSum[i][j + 1] + matrix[i][j];
                colSum[i + 1][j + 1] = colSum[i + 1][j] + matrix[i][j];
            }
        }

        int result = 0;
        for (int i = 1; i <= row; i++) { // 행
            for (int j = 1; j <= column; j++) { // 열
                // if (matrix[i][j] == 1) { // 시작점
                    // result++; // 크기가 1인 정사각형 존재

                    // 최대 크기의 정사각형 구하기
                    // int repeat = Math.min(row - i, column - j);
                    int repeat = Math.min(row - i + 1, column - j + 1);
                // k: 정사각형의 크기
                for (int k = 1; k <= repeat; k++) {
                    // // 정사각형이라면
                    if (rowSum[i+k-1][j+k-1] - rowSum[i-1][j+k-1] == k &&
                        colSum[i+k-1][j+k-1] - colSum[i+k-1][j-1] == k) {
                        result++;
                    } else {
                        break;
                    }
                }

            }
        }

        return result;
    }
}

오늘 회고

너무 어렵다.
내일부턴 비기기너 풀꺼다.
말리지 마라.