[프로그래머스][Level2] 가장 큰 정사각형 c++

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

프로그래머스

 

풀이 과정

가장 큰 정사각형 문제는 오른쪽 아래의 숫자를 잘 봐야된다.  
초기값은 board 0, 0 배열의 값으로 두고, board 배열의 값이 1이 될 때  
(i - 1, j), (i, j - 1), (i - 1, j - 1) 이 중에서 가장 작은 값을 찾은 뒤 + 1를 해주면 된다.

가장 큰 값을 찾아 제곱을 해주면 답이다.

 

풀이 1

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

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

 

풀이 2

#include <vector>
using namespace std;

int max(int a, int b){
    return a > b ? a : b;
}
int min(int a, int b){
    return a > b ? b : a;
}
int solution(vector<vector<int>> board)
{
    int answer = board[0][0];
    for(int i = 1; i < board.size(); i++){
        for(int j = 1; j < board[i].size(); j++){
            if(board[i][j] == 1){
                board[i][j] = 1 + min(min(board[i][j - 1], board[i - 1][j]), board[i - 1][j - 1]);
                answer = max(board[i][j], answer);
            }
        }
    }
    answer *= answer;
    return answer;
}