[백준] 색종이 - 3

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

2571번: 색종이 - 3

색종이가 덮고 있는 영역이라면 넓이를 구하는 방식으로 풀이하였습니다. 시작점을 기준으로 x 좌표를 늘려가면서 해당 width를 기준으로 얻을 수 있는 최대 영역의 넓이를 구하는 방식으로 구하였습니다. height의는 현재까지 만난 길이중 가장 짧은 길이에 의해 결정이 되게 됩니다.

 

import sys
#sys.stdin = open("input.txt", "r")
INT_MAX = sys.maxsize

input = sys.stdin.readline

n = int(input())

MAX_N = 103
length = 10

white = [
    [0] * MAX_N
    for _ in range(MAX_N)
]

for _ in range(n):
    x, y = tuple(map(int, input().split()))

    for i in range(y, y + length):
        for j in range(x, x + length):
            white[i][j] = 1

def getArea(y, x):
    nx = x
    area = 0
    min_len = INT_MAX
    # x를 한칸씩 늘려가면서 얻을 수 있는 직사각형의 최대 넓이를 구한다.
    while x < MAX_N and white[y][nx] == 1:
        ny = y
        while y < MAX_N and white[ny][x] == 1 and white[ny][nx] == 1:
            ny += 1
        # 현재 x, nx가 한변인 직사각형에서 얻을 수 있는 직사각형의 넓이
        min_len = min(ny - y, min_len)

        area = max(area, (nx - x + 1) * min_len)
        nx += 1

    return area


ans = 0

for i in range(MAX_N):
    for j in range(MAX_N):
        # 색종이가 덮고 있는 구역인 경우
        if white[i][j] == 1:
            ans = max(ans, getArea(i, j))

print(ans)