📘 문제

이전에 풀어본 색종이 문제의 업그레이드 버전을 가져왔다.
문제링크 : https://www.acmicpc.net/problem/2571

📝 문제 풀이

이번 문제는 누적합을 이용하는 문제이다. 최근 단계별로 풀기 중 구간합(누적합) 부분에서 새로운 문제를 풀었는데 어려웠다. 이번 문제를 통해서 누적합에 대해서 정리해야지 했는데, 누적합을 사용하는 방식이 달랐다. 전에 문제처럼 접근하려고 노력하다 결국 포기하고 문제를 찾아봤다.(찾아본 블로그 링크)
해당 문제를 보고 문제에 대한 접근 방식을 알게되었다. 해당 문제를 2차원의 누적합을 계산하여 구간합으로 풀려했던 접근방식은 잘못되었고, 링크의 블로그 처럼 좌표평면에서 높이나 넓이 중 하나를 기준으로 누적합을 계산하여 사용했다.

구현한 알고리즘 순서는 다음과 같다

1. 필요한 입력을 받는다.
2. 입력받은 사각형에 해당하는 부분을 1로 세팅한다.
3. 큰 사각형에서 누적합을 계산한다.
4. 계산한 누적합을 가지고 모든 점에서 만들 수 있는 사각형의 넓이를 계산하여 max값을 갱신한다.
   ❗️사각형 넓이 max값 갱신 코드 => answer = max(answer, h*(k-j+1));

✏️ 알고리즘 스케치

빨간색으로 동그라미 친 곳에서 사각형의 넓이들을 구할 때이다. 높이가 4일때 사각형의 넓이를 계속 구하면 넓이는 4, 8, 12, 16 이렇게 구해지고 그 다음 넓이가 3으로 감소했으므로 3*5=15, 18, 21 로 구해지며 해당 점에서 가장 큰 사각형의 넓이는 21이 된다.
이러한 과정을 모든 점에서 실행하면 모든 구간에서 가장 큰 사각형의 넓이를 구할 수 있다.

💻 소스코드

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


void input(int* Nptr, int** x, int** y);
void setPrefixSum(int* arr);
void setRectangle(int* arr, int x, int y);
void setRectangles(int* arr, int* x, int* y, int N);
void findMaxRectangleArea(int* arr);

int main()
{
    int N;
    int *x, *y;
    int arr[101*101];
    fill(arr, arr+101*101, 0);
    input(&N,&x,&y);
    setRectangles(arr,x,y,N);
    setPrefixSum(arr);
    findMaxRectangleArea(arr);
    return 0;
}

void input(int* Nptr, int** x, int** y)
{
    cin >> *Nptr;
    *x = new int[*Nptr];
    *y = new int[*Nptr];
    for(int i=0; i<*Nptr; i++){
        cin >> (*x)[i] >> (*y)[i];
    }
}

void setPrefixSum(int* arr)
{
    for(int i=100; i>=0; i--){
        for(int j=1; j<101; j++){
            if(arr[i*101+j]==1)
                arr[i*101+j] = arr[(i+1)*101+j] + 1;
        }
    }
}

void setRectangle(int* arr, int x, int y)
{
    for(int i=x; i<x+10; i++){
        for(int j=y; j<y+10; j++){
            arr[101*i+j] = 1;
        }
    }
}

void setRectangles(int* arr, int* x, int* y, int N)
{
    for(int i = 0; i<N; i++){
        setRectangle(arr,x[i],y[i]);
    }
}

void findMaxRectangleArea(int* arr)
{
    int answer = 0;
    for(int i=100; i>=1; i--){
        for(int j=1; j<101; j++){
            int h = 100;
            for(int k=j; k<=100; k++){
                h = min(arr[i*101+k], h);
                if(h==0)
                    break;
                answer = max(answer, h*(k-j+1));
            }
        }
    }
    cout << answer << endl;
}