[BOJ] 백준 2571 색종이 - 3

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

 Input 

3

3 7

15 7

5 2

 

 Output 

120

완전 탐색방법으로 6중 for문을 이용할 수 있습니다.

① board[][] 배열에 『1』 로 표시된 모든 지점을 찾습니다.

② 찾은 지점에서 가로 길이 w, 세로길이 h를 조절해서 사각형 영역 설정

③ 사각형 영역 내부가 모두  『1』 로 되어 있는지 확인합니다.

     → 영역 내부에서 모두 『1』 인 경우 너비를 비교해서 최대 넓이 값을 구합니다.

[구현 코드] → O(N6)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int board[101][101];
int ans = 0;
inline int max(int A, int B) { if (A > B) return A; return B; }
void pastePaper(int r, int c) {
    int i, j;
    for (i = r; i < r + 10; ++i) {
        for (j = c; j < c + 10; ++j) {
            board[i][j] = 1;
        }
    }
}
int isBlackPaper(int r, int c, int w, int h) {
    int i, j;
    for (i = r; i <= r + h; ++i) {
        for (j = c; j <= c + w; ++j) {
            // 어느 한 지점이라도 1이 아닌 경우
            if (board[i][j] != 1)
                return 0;
        }
    }
    return 1;
}
void check(int r, int c) {
    int w, h;
    // 가로 크기 증가
    for (w = 0; w < 100; w++) {
        // 범위를 벗어나거나 중간에 흰 영역인 경우
        if (c + w > 100 || board[r][c + w] == 0)
            break;
         
        // 세로 크기 증가
        for (h = 0; h < 100; h++) {
            // 범위를 벗어나거나 중간에 흰 영역인 경우
            if (r + h > 100 || board[r + h][c] == 0)
                break;
            // 가로 길이 = w, 세로 길이 = h
            if (isBlackPaper(r, c, w, h))
                ans = max(ans, (w + 1) * (h + 1));  
        }
    }
}
int main() {
    // freopen("input.txt", "r", stdin);
    int N, i, j, r, c;
    scanf("%d", &N);
    for (i = 0; i < N; ++i) {
        scanf("%d %d", &r, &c);
        pastePaper(r, c);
    }
    for (r = 1; r <= 100; ++r) {
        for (c = 1; c <= 100; ++c) {
            if (board[r][c] == 1)
                check(r, c);
        }
    }
    printf("%d\n", ans);
}

 

세로 구간에 대한 누적 합을 구합니다. board[i][j] = 영역의 높이로 생각할 수 있습니다.

특정 지점에서 그릴 수 있는 가장 큰 사각형은 어떻게 구할 수 있을까?

해당 지점(사각형의 왼쪽 아래)값이 『4』 이므로 이때, 사각형의 최대 높이를 『4』로 초기화 합니다.

우측으로 뻗어나가면 가로(width)를 늘려가고, board[][] 값을 통해 높이 확인합니다.

처음 기준값 『4』 이기 때문에 최대 높이는 4로 볼 수 있습니다. 

따라서 board[][] 값이 큰 수가 있더라도 사각형의 높이를 크게 늘릴 수는 없으며 

board[][] 값이 작아진다면 높이가 작아집니다.

if) board[8][6] = 6을 기준점으로 했다면 3개의 사각형을 그릴 수 있습니다.

▶ board[][] > 0 탐색을 위한 이중 for문 → O(N2)

    width 증가시키면서 동시에 가능한 높이 갱신해 넓이를 구하는 과정 → O(N)

---

[제출 코드] → O(N3)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int board[101][101];
int ans = 0, area;
inline int max(int A, int B) { if (A > B) return A; return B; }
inline int min(int A, int B) { if (A < B) return A; return B; }
void pastePaper(int r, int c) {
    int i, j;
    for (i = r; i < r + 10; ++i) {
        for (j = c; j < c + 10; ++j) {
            board[i][j] = 1;
        }
    }
}

int solve() {
    // 각 줄에 높이 구하기
    for (int i = 1; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            // 중간에 비어있는 부분인 경우
            if (board[i][j] == 0) continue;
            board[i][j] += board[i - 1][j];
        }
    }
    
    for (int r = 1; r < 100; r++) {
        for (int width = 0; width < 100; width++) {
            int height = 100;
            for (int k = width; k < 100; k++) {
                // 시작 위치부터 체크해서 가장 낮은 높이 구하기
                height = min(height, board[r][k]);

                // 높이가 0으로 더 이상 크기를 증가시킬 수 없는 경우
                if (height == 0) break; 

                area = height * (k - width + 1);
                ans = max(ans, area);
            }
        }
    }
    return ans;
}

int main() {
    // freopen("input.txt", "r", stdin);
    int N, i, j, r, c;
    scanf("%d", &N);
    for (i = 0; i < N; ++i) {
        scanf("%d %d", &r, &c);
        pastePaper(r, c);
    }

    printf("%d\n", solve());
}