1915 - 가장 큰 정사각형

정보

• 문제 보기: 1915 - 가장 큰 정사각형
• 소요 시간: 19분 47초
• 풀이 언어: python
• 체감 난이도: 2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

DP

풀이 코드

정보

• 메모리: 67180 KB
• 시간: 2756 ms

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = 0, 0
table, memo = [], []
def dp(i, j):
    global memo
    
    if table[i][j] == 0:
        return 0
        
    if ~memo[i][j]:
        return memo[i][j]
    
    a, b, c = 0, 0, 0
    
    if j+1 < m:
        a = dp(i, j+1)
    if i+1 < n:
        b = dp(i+1, j)
    if i+1 < n and j+1 < m:
        c = dp(i+1, j+1)
    
    res = min(a, b, c) + 1
    
    memo[i][j] = res
    return res
    

def solution():
    global n, m, table, memo
    
    n, m = map(int, input().split())
    for _ in range(n):
        table.append([int(x) for x in list(input().rstrip())])
        
    memo = [[-1 for _ in range(m)] for _ in range(n)]
    
    ans = 0
    for i in range(n):
        for j in range(m):
            if table[i][j] == 1:
                ans = max(ans, dp(i, j))
                
    print(ans*ans)

if __name__ == '__main__':
    solution()

풀이 해설

다음 그림과 같이, 하나의 칸은 인접한 3칸의 최소값에서 + 1한 만큼의 너비로 정사각형을 형성할 수 있다.

⚡ 점화식

$dp(i, j)$ = $min(\:dp(i, j$+$1),\:dp(i$+$1, j),\:dp(i$+$1, j$+$1)\:)$ + $1$

따라서 점화식은 다음과 같이 정의될 수 있다. (i, j 범위에 따른 수식 분기는 생략)

해당 점화식에 따라 구현하면 심플하게 풀이가 끝난다.

📌(i, j) 칸의 값이 0인 경우

if table[i][j] == 0:
    return 0

base case로써 처리된다.

📌bound에 걸리는 경우

a, b, c = 0, 0, 0

if j+1 < m:
    a = dp(i, j+1)
if i+1 < n:
    b = dp(i+1, j)
if i+1 < n and j+1 < m:
    c = dp(i+1, j+1)

bound에 걸리는 경우, 위 로직에서 if문에 진입하지 못함으로써 처리된다.

메모

• 이건 원트 성공~

🙂🙃🙂