[백준] 2571번 : 색종이 - 3 - Python(파이썬)

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

2571번: 색종이 - 3

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록

www.acmicpc.net

풀이
for문 돌며 완전 탐색
board에 1로 된 지점 찾기
해당 지점에서 가로, 세로 너비 조정해 영역 설정
내부가 모두 1인 경우 최대 넓이 구하기

코드

#문제  : https://www.acmicpc.net/problem/2571

import sys

arr = [[0] * 100 for _ in range(100)] #색종이 도화지에 붙인 상태 변수 선언
N = int(sys.stdin.readline()) #색종이 갯수
for _ in range(N):
    width, height = map(int, sys.stdin.readline().split()) #왼쪽 변 거리, 아래쪽 변 거리
    for i in range(10): #도화지 붙이기
        for j in range(10):
            arr[width+i][height+j] = 1

for x in range(100): #전체 돌며 
    for y in range(100):
        if arr[x][y]: #해당 부분인 1이면
            arr[x][y] += arr[x - 1][y] #각 줄의 높이 구하기


ans = 0
for x in range(100):
    for y in range(100):
        height = 100 #최대 높이로 임시로 설정
        for z in range(y, 100): #시작 위치부터 체크해서 가장 낮은 높이 구하기
            height = min(height, arr[x][z]) #가장 작은 값으로 갱신
            ans = max(ans, height * (z - y + 1))
print(ans)