[프로그래머스] Lv2 - 가장 큰 정사각형 찾기 (파이썬)

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

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

 

def solution(board):
    N, M = len(board), len(board[0])
    dp = [[0 for _ in range(M)] for _ in range(N)]
    for i in range(N):
        dp[i][0] = board[i][0]
    for j in range(M):
        dp[0][j] = board[0][j]
    for i in range(1, N):
        for j in range(1, M):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
    result = 0
    for x in dp:
        result = max(result, max(x))
    return result**2

 

DP
1. N과 M을 주어진 board를 이용해서 정의
2. dp 테이블 정의
3. 맨 위와 맨 왼쪽의 dp 초기값을 board값으로 초기화
4. dp (이중 포문)
    - board의 해당 위치가 1이라면
    - dp[i][j] = 위, 왼쪽, 대각의 dp값의 최솟값 + 1
5. dp 테이블 중 가장 큰 값의 제곱 값 반환

 

dp는 너무 오랜만에 풀어봤다.

노트에 적으면서 규칙을 파악했다. 감이 많이 죽었다..