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

문제 

배열에서 1로 된 가장 큰 정사각형의 크기를 구해라! 

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

풀이

DP를 이용하겠다! 

cache[r][c] = min(min(cache[r + 1][c], cache[r + 1][c + 1]), cache[r][c + 1])+1;

 

cache배열에서 제일 아래 행, 오른쪽 열은 table과 똑같이 채워준다. 

그 후에 반복문을 돌면서, table값이 0이면 0으로 채우고 넘어가고, 

0이 아니면 아래 그림과 같이 cache[r + 1][c], cache[r + 1][c + 1], cache[r][c + 1]값들 중에 최솟값 +1을 채우면 된다.

 

위의 알고리즘에 따라 cache배열을 모두 채우면 맨 오른쪽과 같다 

코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int cache[1000][1000];
int table[1000][1000];

int main(void) {
	int n, m;
	cin >> n >> m;
	
	int maxS = 0;
	for (int i = 0;i < n;i++) {
		string s;
		cin >> s;
		for (int j = 0;j < m;j++) {
			table[i][j] = s[j] - '0';
		}
	}
	for (int r = 0;r < n;r++) {
		cache[r][m - 1] = table[r][m - 1];
		maxS = max(maxS, cache[r][m - 1]);
	}
	for (int c = 0;c < m;c++) {
		cache[n - 1][c] = table[n - 1][c];
		maxS = max(maxS, cache[n - 1][c]);
	}
	for (int r = n - 2;r >= 0;r--) {
		for (int c = m - 2;c >= 0;c--) {
			if (table[r][c] == 0)
				cache[r][c] = 0;
			else {
				cache[r][c] = min(min(cache[r + 1][c], cache[r + 1][c + 1]), cache[r][c + 1])+1;
				maxS = max(maxS, cache[r][c]);
			}
		}
	}
	cout << maxS*maxS << endl;
	return 0;
}

 

메모리 사용을 줄이려고 노력해본 코드 

- cache 배열 없애고, table을 그대로 사용 

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int table[1000][1000];

int main(void) {
	int n, m;
	cin >> n >> m;
	
	int maxS = 0;
	for (int i = 0;i < n;i++) {
		string s;
		cin >> s;
		for (int j = 0;j < m;j++) {
			table[i][j] = s[j] - '0';
			if (table[i][j] == 1)
				maxS = 1;
		}
	}
	for (int r = n - 2;r >= 0;r--) {
		for (int c = m - 2;c >= 0;c--) {
			if (table[r][c] == 0)
				continue;
			else {
				table[r][c] = min(min(table[r + 1][c], table[r + 1][c + 1]), table[r][c + 1])+1;
				maxS = max(maxS, table[r][c]);
			}
		}
	}
	cout << maxS*maxS << endl;
	return 0;
}

결과

놀랍게도 시간은 전혀 줄어들지 않았다! 

 

크기가 큰 배열을 선언할 때는, main 함수 바깥에 전역으로 선언해야 오류가 나지 않는다 

(main함수 내부에 선언했더니 코드가 실행중에 꺼지는 현상 발생)