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

문제 링크 => 1915번: 가장 큰 정사각형 (acmicpc.net)

1915번: 가장 큰 정사각형

 

다이나믹 프로그래밍 문제이다.

 

 

 

 

 

 

 

위와 같이 (i - 1, j - 1) 일때의 최대 넓이와 현재 (i, j) 로부터 왼쪽으로의 1의 최대 갯수와 윗쪽으로의 1의

최대 갯수를 활용하여 현재 (i, j) 의 원소가 0, 1인지를 구분하여서 접근하면 된다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>

#define INF 100000000

using namespace std;

int LEFT[1001][1001], UP[1001][1001];
int d[1001][1001], A[1001][1001];
int n, m;

int solution(int A[][1001], int n, int m) 
{
	int min_left_up, beforeS, ret;

	// Set the LEFT Table
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (A[i][j]) LEFT[i][j] = LEFT[i][j - 1] + 1;
			else LEFT[i][j] = 0;
		}
	}
	// Set the UP Table
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (A[j][i]) UP[j][i] = UP[j - 1][i] + 1;
			else UP[j][i] = 0;
		}
	}

	// Dynamic Programming
	ret = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (A[i][j]) {
				min_left_up = min(LEFT[i][j], UP[i][j]);
				beforeS = sqrt(d[i - 1][j - 1]);
				if (min_left_up > beforeS)
					d[i][j] = (beforeS + 1) * (beforeS + 1);
				else
					d[i][j] = min_left_up * min_left_up;
			}
			else d[i][j] = 0;
			ret = max(ret, d[i][j]);
		}
	}

	return ret;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= m; j++)
			A[i][j] = s[j - 1] - '0';
	}
	cout << solution(A, n, m);

	return 0;
}