[프로그래머스][level2] 가장 큰 정사각형 찾기 -python

문제 링크

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

코딩테스트 연습 - 가장 큰 정사각형 찾기

풀이 

- 분할정복으로 푸는 문제인 줄 알았는데 dp 문제였다 

- 가장 윗줄과 가장 왼쪽 줄은 정사각형이 될 수 없으므로, 둘째줄 두번째 칸부터 시작 

- board에 누적되어 저장되는 값은 현재까지 가장 큰 정사각형의 한 변의 길이이다. 

 

1. 

board[i][j] 칸에 저장된 값이 0이 아닐 때,

board[i-1][j-1], board[i][j-1], board[i-1][j] 모두 0이 아니면 정사각형이 가능하다는 것이다. 

 

따라서 board[i-1][j-1], board[i][j-1], board[i-1][j] 최솟값에 + 1을 해준 값을 저장한다. 

 

2. board에 저장된 최댓값을 구한 후 넓이를 리턴한다. 

def solution(board):
    
    for i in range(1, len(board)):
        for j in range(1,len(board[i])):
            if board[i][j] >= 1 :
                board[i][j] = min(board[i-1][j-1], board[i][j-1], board[i-1][j]) + 1
    answer = 0 
    
    for i in board:
        answer = max(answer,max(i))
        
    return answer * answer