2571번 색종이 - 3

https://www.acmicpc.net/problem/2571

 

 

문제 풀이

 

1. 높이 누적합

2. 한 좌표(r, c)에 대해서 모든 경우의 수에 따른 사각형 넓이 구하기(simulation, getValue 함수)

3. 높이(세로)와 가로 길이 구할 때 조심. 높이는 항상 최솟값.

   높이 : 그 열의 맨 아래에 있는 좌표값 + 1 - 자신의 현재 좌표 값

   가로 : (r, c) ~ (r, j)에 해당 하는 단순 가로의 길이이므로, j - c + 1

 

 

 

 

 

2571.xlsx

0.01MB

 

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 101

int n, ans, p[MAX][MAX];

void draw(int r, int c)
{
    for (int i = r; i < r + 10; i++) {
        for (int j = c; j < c + 10; j++) {
            p[i][j] = 1;
        }
    }
}

void height()
{
    for (int i = 1; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (p[i][j] != 0) {
                p[i][j] += p[i - 1][j];
            }
        }
    }
}

int getHeight(int r, int c)
{
    int ret = 0;

    for (int i = r; i < MAX; i++) {
        if (p[i][c] == 0) {
            break;
        }

        // 현재 좌표(r, c)에서의 높이는 
        // 그 열의 맨 아래(최댓값)에 현재 자신의 좌표에 대한 값(p[r][c])을 빼주고 1을 더한다.
        ret = max(ret, p[i][c] + 1 - p[r][c]);
    }

    return ret;
}

int getWidth(int r, int c)
{
    int ret = 1;

    for (int j = c; j < MAX; j++) {
        if (p[r][j] == 0) {
            break;
        }
        ++ret;
    }

    return ret;
}

int getValue(int r, int c)
{
    // (r, c)에 대해서 c가 점점 오른쪽으로 증가하면서 그에 따른
    // 높이를 알맞게 구하여 사각형 넓이를 셈한다.
    // 이때, 높이는 오른쪽으로 갈 수 록 그 중간에 작아질 수 있으므로, 항상 min을 통해 갱신한다.

    int ret = 0, h = INT32_MAX;

    for (int j = c; j < MAX; j++) {
        if (p[r][j] == 0) {
            break;
        }
        h = min(h, getHeight(r, j));
        ret = max(ret, h * (j  - c + 1));
    }

    return ret;
}

void simulation()
{
    for (int i = 1; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (p[i][j] != 0) {
                // 0이 아닌 좌표(i, j)에 대하여 시뮬레이션
                int getAnswer = getValue(i, j);
                ans = max(ans, getAnswer);
            }
        }
    }
}

void print()
{
    printf("■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■\n");
    for (int i = 0; i < 28; i++) {
        for (int j = 0; j < 28; j++) {
            if (p[i][j] == 0) {
                printf("   ");
            }
            else {
                printf("%2d ", p[i][j]);
            }
        }
        printf("\n");
    }
}

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);

    int minx = MAX, maxx = 0, miny = MAX, maxy = 0;

    scanf("%d", &n);

    int x, y;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &x, &y);
        draw(y, x); // y, x 구분 조심
    }

    height(); // 한 좌표(r, c)에서의 높이 누적합(그림 참고)
    print();
    simulation();

    printf("%d\n", ans);

    return 0;
}