[Programmers] 가장 큰 정사각형 찾기

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

백준에도 똑같은 DP 문제가 있었던 것 같습니다.

(y, x) 기준으로 왼쪽, 좌상단, 위쪽 블록이 모두 1 이상이라면 정사각형의 일부라고 생각하면 됩니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	bool isZero(vector<vector<int>> &board)
	{
	for (vector<int> b : board)
	{
	for (int a : b)
	{
	if (a)
	{
	return false;
	}
	}
	}
	return true;
	}
	int solution(vector<vector<int>> board)
	{
	if (isZero(board))
	{
	return 0;
	}
	int answer = 1;
	for (int i = 1; i < board.size(); i++)
	{
	for (int j = 1; j < board[i].size(); j++)
	{
	if (!board[i][j])
	{
	continue;
	}
	board[i][j] = min({ board[i - 1][j], board[i][j - 1], board[i - 1][j - 1] }) + 1;
	answer = max(answer, board[i][j] * board[i][j]);
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~