091 가장 큰 정사각형

첫번째 코드

 

dp를 대표하는 문제 종류 중 하나라고 한다.

2차원 matrix의 경우에도 점화식에 유의하여 작성하며 방법에 대해 공부하자!

 

코드는 책을 참고하였다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dp = [[0 for _ in range(1001)] for _ in range(1001)]
max = 0

for i in range(n):
    numbers = list(input())
    for j in range(m):
        dp[i][j] = int(numbers[j])
        if dp[i][j] == 1 and j > 0 and i > 0:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + dp[i][j]
        if max < dp[i][j]:
            max = dp[i][j]

print(max * max)

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1915.%E2%80%85%EA%B0%80%EC%9E%A5%E2%80%85%ED%81%B0%E2%80%85%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95

programmers/백준/Gold/1915. 가장 큰 정사각형 at main · ornni/programmers