프로그래머스, 가장 큰 정사각형 찾기 : C++ [CPP]

솔직히

나는 해법을 찾지 못해서 다른 사람 풀이를 찾아왔다.

Brute Force에서 케이스를 나누어가며 최대한 줄여봤지만

효율성에서 박살났다.

 

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 = board[0][0]; // 시작
    int r = board.size(); //행
    int c = board[0].size();//열
    
    //왼쪽, 왼쪽 위, 위쪽이 존재해야 하기 때문에
    //(1,1) 부터(r-1,c-1)까지만 조사하면 된다.
    for(int i=1;i<r;i++)
    {
        for(int j=1;j<c;j++)
        {
            //만약 1이라면 3가지 위치 조사해서 더함 
            if(board[i][j]==1){
                //-> 3개가 다 x이라면 -> 3가지의 최솟값이 x라면 
                //-> x이상이라면 -> 해당 값은 x크기의 정사각형의 맨 오른쪽아래임
                board[i][j] = 1 + min({board[i-1][j-1],board[i-1][j],board[i][j-1]});
                //해당 위치를 가장 오른쪽 아래로하는 크기가 1 커진 정사각형이 만들어짐
                answer = max(answer,board[i][j]);
            }
        }
    }
    
    return answer*answer;
}

 

이것은 정사각형은 자신보다 작은 정사각형으로 표현할 수 있다는 점을 알고

자신보다 변의 길이가 1 작은 정사각형으로 자신을 어떻게 표현할 것인가 생각해보면 알 수 있다.

하지만 쉽지 않아서.. 나는 찾아봤다.