📒활용개념

1.정형화된 DP 알고리즘이 존재하여 확인하고 숙지해야한다.
2. 넓이를 직접 구하지 않고 변의 길이를 비교한다.
3. DP와 Memoization

📌문제설명

1와 0으로 채워진 표에서 1로 이루어진 가장 큰 정사각형의 넓이를 구하시오.
ex)
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
표-> 2차원 배열, 행<1000, 열<1000

answer=9

📌구현

#include <iostream>
#include<vector>

using namespace std;

int solution(vector<vector<int>> board)
{ 
	//board가 1X1크기일 때의 예외처리
    int answer=board[0][0];
    
    for(int i=1; i<board.size(); i++){    					
    //행 크기-1만큼 확인
        for(int j=1; j<board[0].size(); j++){ 
        //열 크기 -1 만큼 확인
            if(board[i][j]>0){
            //1이상인 부분만 확인
                board[i][j]+=min(board[i-1][j-1], min(board[i][j-1], board[i-1][j]));
                //알고리즘 확인
                if(board[i][j]>answer){
                    answer=board[i][j];
                }
            }
            
            else{
                continue;
            }
        }
    }
    
    //사각형 넓이 구하기
    answer*=answer;
    
    return answer;
}

📌주의점

• DP를 이용한 알고리즘을 활용한다.
• 넓이를 직접 구하지 않고 변의 길이를 구하는 것이 더 빠르고 쉽다.
• 어떤 예외가 있는지(ex, board의 크기가 1*1인 경우) 고민해야한다.