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

예전에 fastcampus에서 한번 다뤘던 문제라고 기억을 하는데

이미 기억에서 지워진 문제

 

DP로 푸는것만 기억하고 나머지는 다 잊어버림

 

 

def solution(board):
  
    width = len(board[0])
    height = len(board)

    for x in range(1,height):
        for y in range(1,width):
            if board[x][y] == 1:
                board[x][y] = min(board[x-1][y-1], min(board[x-1][y], board[x][y-1])) + 1
    return max([item for row in board for item in row])**2

출처:geonlee.tistory.com/111

 

굳이 DP list를 만들겠다면

def solution(board):
  
    width = len(board[0])
    height = len(board)
    DP = [[0 for _ in range(width)] for _ in range(height)]
    
    for x in range(1,height):
        for y in range(1,width):
            if board[x][y] == 1:
                DP[x][y] = min(DP[x-1][y-1], min(DP[x-1][y], DP[x][y-1])) + 1
    for a in DP:
      print(a)
    return max([item for row in DP for item in row])**2