Gidhub BE Developer

Programmers - 가장 큰 정사각형 찾기

2018-07-25
goodGid

Problem

Problem URL : 가장 큰 정사각형 찾기


[1] Answer Code (18. 07. 25)


int dp[1001][1001];

int solution(vector<vector<int>> board){
    int answer = 0;
    int r_size = (int)board.size();
    int c_size = (int)board[0].size();
    
    for(int i=0; i<r_size; i++){
        for(int j=0; j<c_size; j++){
            if( i==0 || j == 0) {
                dp[i][j] = board[i][j];
                answer = answer < dp[i][j] ? dp[i][j] : answer; // [1]
                continue;
            }
            if(board[i][j]){
                dp[i][j] = min({ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] }) + 1;
                answer = answer < dp[i][j] ? dp[i][j] : answer;
            }
        }
    }
    
    answer *=  answer;
    
    return answer;
}


[1] Answer Code (18. 07. 25)

  • 구현만 생각하다보니 너무 어렵게 접근했다.

  • DP를 생각못했다. 다시 풀어봐야지 !

  • [1]을 뺴고 제출했더니 TC 1만 틀리더라 …
    [ 1 1 ] 이렇게 들어왔을 때 [1]이 없으면 0을 Return한다.


Comments

Content