문제

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

나의 코드 (답안참조)

"""
1. 아이디어
그냥 dp문제라고 직감이 오긴했는데 구현력이 딸려서 실패..

2. 시간복잡도
O(N^2)이지 않나 싶다.. O(N^3)으로 보일 순 있는데 min연산은 3개 하고만 비교하기 때문에 상수값은 무시하는걸로 해도된다.
"""

def solution(board):

    n = len(board)
    m = len(board[0])
    
    for i in range(1, n):
        for j in range(1, m):
            if board[i][j] == 1:
                board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1
    
    line = 0 # 2*2 배열일때 전부 0일수도 있으니 1이 아니라 0으로 초기화 해줘야함, 1해주니깐 틀림

    for i in range(n):
        tmp = max(board[i])
        line = max(line, tmp)
            
    return line ** 2
    

느낀점

어휴.. 완전탐색으로 풀기엔 딱봐도 3중 for문을 넘어갈꺼 같아서 n의 범위를 보니깐 답도 안나와서 dp문제라고 생각하긴 했는데 구현력이 딸려서 실패했다;; dp문제 많이 풀어서 구현 능력좀 길러야지..

참고자료

이 문제에 대해 잘 정리해주셔서 참고 많이 했다.
https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95-%EC%B0%BE%EA%B8%B0-%EB%8F%99%EC%A0%81-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-dp