프로그래머스 2레벨 12905 가장 큰 정사각형 찾기

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/12905

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

풀이

배열의 각 요소를 왼쪽,위,왼쪽 위의 값 중 최솟값 +1로 갱신하여 최대 크기를 구할 수 있다.
최솟값인 이유는 정사각형이기 때문이다.
현 위치에서 가능한 최대 정사각형의 크기를 저장한다는 점에서 메모라이제이션 느낌을 받았다.

코드

class Solution {
    public static int solution(int [][]board)
    {
        int answer = board[0][0];
        int r = board.length;
        int c = board[0].length;
        for(int i=1;i<r;i++)
        {
            for(int j=1;j<c;j++)
            {
                if(board[i][j] == 1)
                {
                    board[i][j] = Math.min(board[i-1][j],board[i-1][j-1]);
                    board[i][j] = Math.min(board[i][j-1],board[i][j]) + 1;
                    answer = Math.max(answer,board[i][j]);
                }

            }
        }   
        return (int)Math.pow(answer,2);
    }

}

메모

문제는 간단한데 막상 풀려니 풀이가 떠오르지 않은 문제🙃
스스로 풀었는가 : ❎