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

완전탐색으로 구현해야 되나 고민이 많이 되었다.

시간초과가 날 확률이 높아보여서 생각만 하고 시도해보지 않았다.

다른 방법이 떠오르지 않아 검색을 통해 해결했다.

그런데 왠걸..... 또 DP를 이용해야 하는 문제였다......

DP의 개념이 이해하기 힘들었는데 이번 문제를 해결하면서 전보단 많이 정리가 된 것 같다.

그래도 어렵다...

---

최종 코드

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 1234;

         // 계산을 위한 배열 만들기
        int[][] temp = new int[board.length + 1][board[0].length + 1];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                temp[i+1][j+1] = board[i][j];
            }
        }

        int max = 0;
        for (int i = 1; i < temp.length; i++) {
            for (int j = 1; j < temp[i].length; j++) {
                if(temp[i][j] == 1) {
                    int left = temp[i][j-1];
                    int up = temp[i-1][j];
                    int leftup = temp[i-1][j-1];
                    int min = Math.min(left, Math.min(up, leftup));
                    temp[i][j] = min + 1;
                    max = Math.max(max, min + 1);
                }
            }
        }
        answer = max * max;

        return answer;
    }
}