C++ / 프로그래머스 / 가장 큰 정사각형 찾기

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

 

 

문제풀이

 

누적합으로 풀었는데 다 풀고 다른 풀이를 보니 DP로 푼 사람이 많았다...

 

2차원 벡터의 누적합을 구한다.

먼저 x 증가하는 방향으로 누적합을 구한 뒤, y가 증가하는 방향으로 누적합을 구한다.

 

표의 열 또는 행 중 작은 값이 답의 최댓값이 될 수 있으므로, 해당 값부터 시작한다.

한 변의 길이가 len인 정사각형 구간을 반복문을 통해 값을 구한다.

만약 해당 구간의 누적합이 len * len의 값과 같다면 len이 가장 큰 정사각형의 한 변의 길이가 된다.

반복문이 종료될 때까지 같은 값이 없으면 0을 반환한다.

 

위의 구간 누적합을 구하려면

첫 칸부터 구하려는 구간의 맨 오른쪽 맨 아래 부분까지의 누적합에서

파란 부분을 제외한 맨 아래칸까지, 맨 오른 칸까지의 누적합을 빼고, 두 번 뺀 구간인 주황색이 겹치는 구간의 누적합을 더하면 된다.

 

 

코드

 

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

int solution(vector<vector<int>> board)
{
    int N(board.size()), M(board[0].size());

    vector<vector<int>>sum(N + 1, vector<int>(M + 1, 0));

    for (int y = 1; y <= N; ++y) {
        for (int x = 1; x <= M; ++x) {
            sum[y][x] = sum[y][x - 1] + board[y - 1][x - 1];
        }
    }

    for (int y = 1; y <= N; ++y) {
        for (int x = 1; x <= M; ++x) {
            sum[y][x] += sum[y - 1][x];
        }
    }

    for (int len = min(N, M); len > 0; --len) {
        for (int y = 1; y <= N - len + 1; ++y) {
            for (int x = 1; x <= M - len + 1; ++x) {
                if (sum[y + len - 1][x + len - 1] - sum[y + len - 1][x - 1] - sum[y - 1][x + len - 1] + sum[y - 1][x - 1] == len * len) {
                    return len * len;
                }
            }
        }
    }

    return 0;
}