WantAirpod

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

문제 설명
1로 구성된 가장 큰 정사각형의 넓이를 구하는 문제이다.

위와 같은 경우 답은 9이다.

문제풀이 방법
***DP문제****
우측 맨밑 좌표를 기준으로 넓혀가는 느낌...!

1. 0이면 패스한다.
2. 1이 나오면 왼쪽, 위, 왼쪽 대각선의 요소들을 검사한다.

Step1
- 1이 나오면 왼쪽, 위, 왼쪽 대각선의 요소들을 검사한다.
- 왼쪽, 위, 왼쪽 위 대각선에 값이 없으면 pass
- 0이 나오면 X
- 왼쪽, 위, 왼쪽 위 대각선에 값이 1이면 검사했던 값의 최소 값에서 +1 해준다.

Step2
- 해당 값은 정사각형의 한 번의 길이가 된다. 따라서 제곱을 하면 닶.

점화식
board[i][j] = min(board[i-1][j],board[i[[j-1],board[i-1][j-1]) +1;

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int map[1001][1001] = {0,};
int solution(vector<vector<int>> board)
{
    int answer=board[0][0];
    int max = -987654321;
    for(int i = 1 ; i < board.size() ; i++){
        for(int j = 1 ; j < board[i].size() ; j++){
            if(board[i][j]==0)
                continue;
            if(board[i][j]==1){
                board[i][j] = min({board[i-1][j],board[i-1][j-1],board[i][j-1]})+1;
            }
            
            if(board[i][j] > max) {
                max = board[i][j];
            }
        }
    }
    if(max==-987654321){
        answer = board[0][0];
    }else{
        answer = max*max;
    }
    
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    //cout << "Hello Cpp" << endl;

    return answer;
}