[swift] 프로그래머스 - 가장 큰 정사각형 찾기

프로그래머스

---

나의 풀이

func solution(_ board:[[Int]]) -> Int {
    var myBoard = board
    let N = board.count
    let M = board[0].count
    for i in 1..<N {
        for j in 1..<M {
            if myBoard[i][j] > 0 {
                myBoard[i][j] += min(myBoard[i][j-1],myBoard[i-1][j-1],myBoard[i-1][j])
                // 현재 보드의 왼쪽,위쪽,왼위쪽의 값 중 제일 작은 값에 + 1을 하여 현재 보드에 저장
                // why? 세값 모두 1로 다 차있다면 2가되면서 해당 보드를 기준으로 2인 크기의 정사각형이 만들어짐
                // 마찬가지로 세값 모두 2로 차있다면 3인 크기의 정사각형이 만들어질 수 있음
            }
        }
    }
    let num = myBoard.flatMap({$0}).max()!
    return num * num
}

풀이 키워드

DP
모든 알고리즘이 그렇지만..
DP는 문제를 많이 풀어봐야 어떤식으로 접근해야 할지 생각이 나는거 같다.
반대로 DP를 보는눈이 부족하다면 어떻게 풀어야할지 쉽게 생각나지 않는거 같다.

---