[백준] 1915번 가장 큰 정사각형 C++

문제 출처: https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

처음에 TopDown방식으로 접근했으나 잘 되지 않아서 BottomUp방식을 참고하여 풀었다.

 

dp[i][j] 가 N이 되기 위해서는 세방향이 전부 N-1이 되어야 하기 때문에

dp[i][j] =  min({ dp[i - 1][j - 1],dp[i - 1][j],dp[i][j - 1] }) + 1 과 같은 점화식을 세울 수 있다.

 

i==0||j==0인 경우 arr[i][j]로 초기화 해준뒤 반복문을 돌려 해결하였다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>

using namespace std;

int N, M;
int dp[1001][1001];
int arr[1001][1001];
int maxV = 0;


int main(void)

{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string temp; cin >> temp;
		for (int j = 0; j < M; j++) {
			arr[i][j] = temp[j] - '0';
			if (arr[i][j] == 1)maxV = 1;
		}
	}


	for (int i = 0; i < N; i++)dp[i][0] = arr[i][0];
	for (int j = 0; j < M; j++)dp[0][j] = arr[0][j];

	for (int i = 1; i < N; i++) {
		for (int j = 1; j < M; j++) {
			if (arr[i][j] == 1)dp[i][j] = min({ dp[i - 1][j - 1],dp[i - 1][j],dp[i][j - 1] }) + 1;
			if (maxV < dp[i][j])maxV = dp[i][j];
		}
	}

	cout << maxV * maxV;




}