[프로그래머스] Lv.2 가장 큰 정사각형 찾기 - 파이썬(Python) 풀이

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

프로그래머스

 

 

문제 설명

---

문제풀이

 

DP로 풀어야 겠다는 생각을 하기까지 좀 걸린 문제였습니다.. 

아마 DP로 풀지 않으면 효율성 테스트에서 통과되지 않을거에요! 

 

 

현재 위치 값이 1일 경우, 왼쪽 대각선 위, 위, 왼쪽 중 최솟값을 찾아 1더해서 저장합니다.

다음 과정을 계속 반복하면 이런 배열 모습이 나옵니다. 배열에 저장된 값중 최댓값을 찾아 출력하면 됩니다.

 

풀이 코드

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