[백준] 1915-가장 큰 정사각형(C++)

문제링크: https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

dp문제입니다.

 

 

위와 같을때 값을 2*2 =4입니다. 각 점마다 자신의 넓이는 이전 점들의 값과 연관이 있습니다.

 

점화식은 arr[i][j] 가 1인점에 한해서 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1], dp[i][j] ) + 1 입니다. 

이전 값들의 크기에 따라서 값이 변하게 되는 구조입니다.

 

저는 초기값 설정을 어설프게 해서 한번 틀렸었습니다.

1행과 1열 모두 초기값 설정을 해야합니다.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int dp[1001][1001] = { 0 };
int result = 0, n = 0, m = 0;
string arr[1001];

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
			cin >> arr[i];

	for (int i = 0; i < n; i++) {
		dp[i][0] = arr[i][0] - '0';
		result = max(result, dp[i][0]);
	}
	for (int i = 0; i < m; i++) {
		dp[0][i] = arr[0][i] - '0';
		result = max(result, dp[0][i]);
	}

	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], dp[i - 1][j - 1]);
				dp[i][j] = min(dp[i][j - 1], dp[i][j]);
				dp[i][j]++;
			}
			if (result < dp[i][j])
				result = dp[i][j];
		}
	cout << result*result << '\n';
}

 

구현자체에 어려움은 없으실 것입니다.