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

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

 

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

프로그래머스

---

 

해결전략

 

동적계획법 Dynamic Programming, DP

 

다른 방식으로 풀면 시간초과(효율성 테스트 실패)가 나온다.

---

 

 

정답 코드

 

#include <vector>
using namespace std;

int solution(vector<vector<int>> board){
    int row = board.size();
    int col = board[0].size();
    vector<vector<int>> dp(row, vector<int>(col));
    
    if (row == 1 && col == 1) {
        if (board[0][0] == 1) return 1;
        else return 0;
    }

    for (int y = 0; y < row; y++) {
        for (int x = 0; x < col; x++) {
            dp[y][x] = board[y][x];
        }
    }

    int answer = 0;
    for (int y = 0; y < row - 1; y++) {
        for (int x = 0; x < col - 1; x++) 
        {
            if (board[y+1][x+1] == 1)
            {
                dp[y + 1][x + 1] = 1 + min(dp[y][x], min(dp[y + 1][x], dp[y][x + 1]));

                answer = max(answer, dp[y + 1][x + 1]);
            }
        }
    }

    answer = answer * answer;

    return answer;
}

 

 

---

 

 

 

다른 사람의 설명

 

https://soobarkbar.tistory.com/164

 

---