백준 1915 c++ - 가장 큰 정사각형

[필자 처음 생각 ]

처음 문제를 읽고 DFS, BFS 문제라 생각했지만 모든 정사각형인지 판단하려면 코드를 짜는것도 쉽지 않고 무엇보다 시간복잡도 측면에서 어긋나게 된다는걸 알았다. 

다음으로 분할로 사고를 바꿨지만 사각형이 어디에 존재하는지 정확히 알 수 없는 상황에서는 균등하게 분할로 풀 수 없었다.

[해결과정]

조금의 사고 과정후 DP문제라는걸 알게 되었다

 

[KEY POINT]

만약 배열 값이 1이면 사각형 오른쪽 아래 꼭짓점이라 가정을한다.

 

그 점 기준으로 왼쪽, 위쪽, 왼쪽위의 값중 가장 작은값을 구하고 +1을 해주면 동적프로그래밍 완성이다. 

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <cstring>
#include <string.h>
using namespace std;

int Arr[1001][1001];
int N, M;
int D[1001][1001];
int Result = 0;
void Input() {
	cin >> N >> M;
	string str;
	for (int i = 1; i <= N; i++) {
		cin >> str;
		for (int k = 1; k <= str.size(); k++) {
			Arr[i][k] = str[k-1] - '0';
		}
	}

}

void Solve() {
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= M; k++) {
			if (Arr[i][k] == 1) {
				int minNumber = min(D[i - 1][k - 1], D[i - 1][k]);
				D[i][k] = min(minNumber, D[i][k - 1]) + 1;
				Result = max(D[i][k], Result);
			}
			else {
				D[i][k] = 0;
			}
		}
	}

	cout << Result*Result;
}


int main(void) {
	Input();
	Solve();
}