프로그래머스 연습문제 가장 큰 정사각형 찾기 [JAVA] - 22년 9월 23일

시간은 엄청쓰고 풀지는 못해서 정답을 참고했음

해당 블로그 글을 봤으며 설명이 좋다.
https://small-stap.tistory.com/40

//정답 코드 참고 : https://small-stap.tistory.com/40
    //DP를 사용함

class Solution {
    int[][] memo;

    public int solution(int[][] board) {
        memo = new int[board.length + 1][board[0].length + 1];
        int lengthOfMaxSide = 0;

        for (int i = 1; i < board.length + 1; i++) {
            for (int j = 1; j < board[0].length + 1; j++) {
                if(board[i - 1][j - 1] == 0 ) continue;

                int tempLength = Math.min(memo[i][j - 1], Math.min(memo[i - 1][j], memo[i - 1][j - 1])) + 1;
                lengthOfMaxSide = Math.max(lengthOfMaxSide, tempLength);
                memo[i][j] = tempLength;
            }
        }

        return lengthOfMaxSide * lengthOfMaxSide;
    }
}