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

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

 

👩🏻‍💻 코드

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

    return answer**2

 

📝 정리

DP 방식으로 풀면 간단하게 풀리는 문제였다. 나는 아이디어가 생각 안 나서 찾아봤지만..

1. board[i][j]==1이면, board[i][j]를 ( 1 + ↖↑← 방향 중 min값 )으로 설정
2. answer에 max 값 설정
3. 마지막에 answer 제곱 return

 

https://soobarkbar.tistory.com/164 를 참고했다.