99클럽 코테 스터디 21일차 TIL + [LeetCode] 1277. Count Square Submatrices with All Ones / 동적 계획법

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

동적계획법

 

 

2. 오늘의 학습 문제 

---

문제

---

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

 

 

 

코드

---

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length; // dimensions for matrix
        int[][] dp = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) { // cell is in first row or column
                    dp[i][j] = matrix[i][j];
                } else if (matrix[i][j] == 1) {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
                ans += dp[i][j];
            }
        }
        return ans;
    }
}

 

이중 for문을 통해 풀 수 있었다. 

풀이를 참고했다.

 

3. 오늘의 회고

---

 

• 다시 풀어볼 것!
• 세션에서,
• 1. 문제에서 요구하는 것이 무엇인지 파악-> 이 문제의 경우 시간!
• 2. time에 대한 sort는 필요없었음. 
• 3. 완전탐색을 먼저 생각하고, 범위가 안될 것 같으면 이분 탐색을 생각하기