(C++) - 프로그래머스(연습문제) : 가장 큰 정사각형 찾기

dpprogrammers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

dp문제였습니다.

 

풀이방법

 1. 배열 d를 정의합니다. : (i,j) 위치에서 정사각형이 되는 최대 한 변의 길이

다음과 같이 1,1의 위치에서의 정사각형을 만들 수 있는 최대 한 변 길이는 다음과 같은 세 방향으로부터의 값 중 최소가 됩니다.

 

 

 2. 점화식을 세웁니다 : 현재 i,j위치가 1이라면 정사각형의 한 변의 길이를 넓혀 볼 수 있습니다. 넓힐때는 다음과 같이 정사각형의 특성상 영향을 받는 노란색의 나머지 세 위치로부터 값들의 최소를 뽑은 뒤 + 1을 해주면 됩니다. 

    d[i+1][j+1] = min({d[i][j],d[i][j+1],d[i+1][j]}) + 1;

Code

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int>> board){
    int answer = 0;
    int d[1001][1001]; //i,j에서 최대 한 변 길이
    memset(d,0,sizeof(d));
    int r = board.size();
    int c = board[0].size();
    int width = 1;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(board[i][j]) {
                d[i+1][j+1] = min({d[i][j],d[i][j+1],d[i+1][j]}) + 1;
            }
        }
    }
    
    for(int i = 1; i <= r; i++){
        for(int j = 1;j <= c; j++){
            answer = max(answer,d[i][j]);
        }
    }
    return answer * answer;    
}