[알고리즘C++]가장 큰 정사각형

오늘의 문제

어디서 풀어본 것 같은 기분?
https://programmers.co.kr/learn/courses/30/lessons/12905

가장 큰 정사각형

나의 풀이

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

int solution(vector<vector<int>> board)
{
    int answer = 0;
    
    int row = board.size(); // 행
    int column = board[0].size(); // 열
    vector<vector<int>> dp(row, vector<int>(column, 0));
    
    for(int i=0;i<row;i++){ // 초기화
        dp[i][0] = board[i][0];
        answer = max(answer, dp[i][0]);
    }
    for(int i=0;i<column;i++){ 
        dp[0][i] = board[0][i];
        answer = max(answer, dp[0][i]);
    }
        
    for(int i=1;i<row;i++){
        for(int j=1;j<column;j++){
            if(board[i][j] == 1){
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
                answer = max(answer, dp[i][j]);
            }else{
                dp[i][j] = 0;
            }
        }
    }
    return answer * answer;
}

모범 답안

#include<vector>

using namespace std;

int solution(vector<vector<int>> board)
{
    int w = board[0].size(), h = board.size();
    int answer = board[0][0];

    for (int i = 1; i < h; i++) {
        for (int j = 1; j < w; j++) {
            if (board[i][j] != 1) continue;

            int min = board[i-1][j-1];
            if (board[i-1][j] < min) min = board[i-1][j];
            if (board[i][j-1] < min) min = board[i][j-1];
            board[i][j] += min;

            if (board[i][j] > answer) answer = board[i][j];
        }
    }

    return answer * answer;
}

배울 점

• 한번 풀어본것 같은 유형. 방법이 생각나서 뿌듯하다
• 이사람은 그냥 board에 넣어버린다.
• 이중 vector의 크기 선언 방법을 잊어먹었었다. 다시 기억 기억
• vector<vector> vec(6, vector(6, 0)); // 6*6