[프로그래머스/파이썬/가장 큰 정사각형 구하기]

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

def solution(board):
    answer = 0    
    col = len(board)
    row = len(board[0])
    dp = [[0] * row for _ in range (col)]
    
    for i in range (col):
        for j in range (row):
            if board[i][j] == 1:
                dp[i][j] += 1
                if i<1 or j<1 :
                    continue
                dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1
    for a in dp:
        answer = max(answer,max(a))
    return answer**2

---

풀이

제약조건이 다음과 같아서 이중 for문을 사용하면 10의 6승이 되어 더이상 반복문을 돌릴 수는 없을 것 같았다.

• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수

알고리즘

DP를 보자마자 떠올렸고 1일 때 자신의 좌상대각선, 좌, 상으로 정사각형을 만들 수 있으면 될 것 같았다.

이렇게 되는 것을 생각을 했고 상세 그림은 다음과 같다

3방향에서 있는 애들 중 자신이 확실하게 만들 수 있는 정사각형 중 가장 큰 수를 기록해온 dp이므로