Programmers 12905 큰 정사각형 찾기

05 Apr 2021 in Algorithm

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12905

나의 풀이

표의 좌측 상단부터 정사각형의 길이를 구한다.
DP를 이용하여 문제를 풀이하면 시간초과를 해결할 수 있다.

풀이 코드 : 12905 가장 큰 정사각형 찾기

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

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

채점결과