가장 큰 정사각형 찾기

접근법:

DP 테이블 준비
현재 칸이 1 인지 확인하기
1이라면 1행전, 1열전, 왼쪽위 대각선의 값을 확인하고 그중 작은값을 선택하고 + 1 을 한다.
길이의 최댓값을 갱신한다.
넓이를 리턴한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> board)
{
    int max_len = 0;
    int n = board.size();
    int m = board[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0));
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            if(board[i][j] == 1)
            {
                if(i == 0 || j == 0) dp[i][j] = 1;
                else 
                {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1 ]}) + 1;    
                }
               
                max_len = max(max_len, dp[i][j]);
            }
        }
    }
    return max_len * max_len;
}

거리두기 확인하기[프로그래머스]

우박수열 정적분[프로그래머스]