[Python] 프로그래머스. 가장 큰 정사각형 (Level 2)

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

코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스

 

DP를 사용해 풀 수 있는 문제.

 

board의 y좌표, x좌표를 기준으로 볼 때

board[y-1][x-1], board[y][x-1], board[y-1][x] 세 개의 좌표값이 전부 1이라면

board[y][x]는 세 개의 정사각형이 왼쪽, 위쪽, 왼쪽 대각선에 포진해 있게 된다.

따라서 이 경우 결과적으로 정사각형 4개가 붙어 있는 모양이 되므로 변의 길이가 2인 정사각형이 된다.

 

따라서 DP 점화식을

board[y][x] = max(min(board[y-1][x-1], board[y-1][x], board[y][x-1]) +1, board[y][x])

로 세우면 된다.

 

대신 board[y][x] 값이 0인 경우, min() 값이 0인 경우에는 정사각형이 아니므로 점화식에 포함하지 않는다.