프로그래머스 level2 ) 가장 큰 정사각형 찾기

프로그래머스 level2 ) 가장 큰 정사각형 찾기

이 문제를 보고 당연히 그 무작정 완전히 탐석하는 알고리즘? 이름이 뭐였지?? 어째든 그 방싣으로 풀어야할거 같아서
이 방식으로 풀었다.
그치만 결과는 시간초과

class Solution
{
     public static boolean check(int [][]board,int x,int y, int size){
        for(int i=x; i<x+size; i++)
        {
            for(int j=y; j<y+size; j++)
            {
                if(board[i][j]!=1)
                    return false;
            }
        }
        return true;
    }
    public int solution(int [][]board)
    {
         int size=1;
        int answer = 0;
        for(int i=0; i<board.length; i++)
        {
            for(int j=0; j<board[i].length; j++)
            {
                if(board[i][j]==0)continue;
                while(check(board, i,j, size))
                {
                    size++;
                    if(i+size>board.length || j+size>board[i].length)
                        break;
                }
                --size;
                if(answer<size)
                    answer=size;
                size=1;
            }
        }
        answer=answer*answer;
        return answer;
    }
}

어떻게 풀어야할지 고민하던 와중 dp로 풀어야한다는 글을 읽었다.
이걸 어떻게 dp로 풀지 고민하다가
다른 분의 풀이 방법을 보고 구현했다.
이게 왜 dp지 의문이 있었지만
예전에 DP문제에서 본거 같기도 하다

class Solution
{ 
    public int solution(int [][]board)
    {
        int answer = 0;
        for(int i=0; i<board.length; i++)
        {
            for(int j=0; j<board[i].length; j++)
            {
                if(board[i][j]==0)continue;
                if(i-1>=0 && j-1>=0)
                    board[i][j] = 1+Math.min(board[i-1][j-1],Math.min(board[i-1][j],board[i][j-1]));
                if(board[i][j]>answer)
                    answer = board[i][j];
            }
        }
        answer=answer*answer;
        return answer;
    }
}