[프로그래머스]연습문제 : 가장 큰 정사각형 찾기 (level 2)(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 max_area = 0;

    int w = board[0].size();
    int h = board.size();

    // board의 양 변이 2 이하일 수도 있으므로, 전체를 탐색한다.
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            // B[i][j]가 0보다 크면 
            if (board[i][j] > 0)
            {
                // B[i][j]가 2 * 2 사각형의 오른-아래쪽 칸일때
                if (i >= 1 && j >= 1)
                {
                    // B[i][j]는 나머지 3 칸의 최소값 + 1. 
                    // 전체 정사각형의 가장 긴 길이를 뜻한다.
                    board[i][j] = min({ board[i - 1][j], board[i][j - 1], board[i - 1][j - 1] }) + 1;
                }
 
                // 최대길이 찾기
                if (max_area < board[i][j])
                {
                    max_area = board[i][j];
                }
            }
        }
    }

    return max_area * max_area;
}

 

DP로 푸는 것이 "효율적"이다!

다른 방식으로 풀면 답은 나오겠지만 효율성 테스트에서 fail이 난다.

 

TIP

가장 큰 정사각형의 넓이를 찾으려면 

우선 가장 긴 정사각형의 길이를 찾아야 한다.

즉, 가장 긴 정사각형의 길이를 DP를 통해서 갱신해 나가주면 된다.

 

2 * 2 정사각형이 모두 1 이상이라면, 마지막 칸은 새 값(가장 긴 길이)으로 갱신된다. 

 

2 * 2 정사각형의 우측 하단 마지막 칸의 값을, 나머지 3칸의 최소값 + 1로 갱신해준다.

만약 4칸이 모두 1이라면, 마지막 칸의 값은 2가 될 것이고

4칸 중 0과 같이 빈칸이 있다면 마지막 칸 값은 그대로 1가 될 것이다. 

board[i][j]가 마지막 칸일 때를 기준으로 가장 긴 길이의 값을 찾는다.

 

 

근데 board[i][j]가 마지막 칸이 될수 없는 경우는요...?

i < 2, j < 2 일때. board[i][j]의 값에 따라 max의 값을 갱신하자.

 

i < 2, j < 2 일때는 해당 칸의 값에 따라 max를 갱신하면 된다.  

문제에서 input으로 주어진 board의 길이가 2 미만일 때도 커버가 된다.