99클럽 코테 스터디 19일차 TIL, DP(Count Square Submatrices with All Ones)

1. 문제 정의

2. 문제 접근

dp 토픽에 속한 것이니 dp로 풀면 될 것 같다.

3. 문제 풀이

1. dp 배열을 만든다.
2. 점화식을 찾는다.
   1. 결국 사각형을 만들어야 하는데, 한변의 길이가 1~300 사이의 정사각형이 될 것이고, 사각형을 어떻게 만들것인가를 점화식으로 표현하면 된다.
   2. 해당 좌표의 값이 0이 아니면서, 사각형을 이루는 dp값의 최솟값에 1을 더해주면 해당 위치의 사각형 갯수가 된다.
3. 모든 dp 값을 더해준 것을 리턴한다.

4. 코드

class Solution {
    public int countSquares(int[][] matrix) {
        int ans = 0;
        int n = matrix.length;
        int m = matrix[0].length;

        int[][] dp = new int[n][m];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                dp[i][j] = matrix[i][j];
            }
        }

        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                if(dp[i][j] == 1){
                    int min = Math.min(dp[i-1][j], Math.min(dp[i][j-1],dp[i-1][j-1]));
                    dp[i][j] = min+1;      
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                ans += dp[i][j];
            }
        }

        return ans;
    }
}

 

 

 

5. 회고

비슷한 문제가 로봇이 (0,0) 에서 (n,m)까지 가기 위한 최소 이동거리가 있는 것 같다. 그것도 오른쪽, 아래쪽 두 방향 중 최소값을 계속 더해주는 식으로 내려가면 결국 마지막 (n,m)이 되었을 때 최소 이동거리 값이 된다. dp는 역시 많이 풀어보는 수 밖에 없는 듯 하다.