[코드트리 챌린지] 3주차 - 양수 직사각형의 최대 크기

·문제링크

https://www.codetree.ai/cote/13/problems/max-area-of-positive-rectangle&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

·핵심

1. 시간복잡도 : O(nm * nm * nm) = O((nm)^3)

→ board의 모든 좌표 판단 : n * m

→ 가능한 사각형의 모든 모양 : n * m

→ 만들어진 직사각형 안의 격자들이 격자 내부에 존재하며 양수인지 판단 : n * m

2. retangles : 가능한 사각형의 모든 모양 기록 

# 가능한 사각형의 모든 모양 기록
retangles = []
for r in range(1, n + 1):
    for c in range(1, m + 1):
        retangles.append((r, c))

3. 양수 직사각형 판단 : 조건을 만족하는 격자의 수와 직사각형의 넓이 같다면 양수 직사각형

# 격자의 수와 넓이가 같으면 양수 직사각형이다.
if cnt == dr * dc:
    ans = max(ans, dr * dc)

---

·코드(Python)

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
# 격자 내 범위 체크
def in_range(r, c):
    return 0 <= r < n and  0 <= c < m

# 가능한 사각형의 모든 모양 기록
retangles = []
for r in range(1, n + 1):
    for c in range(1, m + 1):
        retangles.append((r, c))

# 시간복잡도 : O(nm * nm * nm) = O((nm)^3)
# 20^6 = 2^6 * 10^6 = 64 * 1000000 = 64,000,000
# 양수직사각형이 없을 경우 -1 출력
ans = -1
for r in range(n):
    for c in range(m):
        for dr, dc in retangles:
            # 새로운 사각형 만들어질 때마다 cnt 초기화
            cnt = 0
            for i in range(r, r + dr):
                for j in range(c, c + dc):
                    if in_range(i, j) and board[i][j] > 0:
                        cnt += 1
            # 격자의 수와 넓이가 같으면 양수 직사각형이다.
            if cnt == dr * dc:
                ans = max(ans, dr * dc)

print(ans)