BOJ-1915-가장 큰 정사각형

[changicho]

1915. 가장 큰 정사각형

링크

난이도	정답률(_%)
Silver I	28.739

설계

메모이제이션

map[y][x]가 정사각형인 경우 (==1) 현재 위치 (y,x)에서 가질수 있는 최대 정사각형의 길이는

memo[y][x] = min(memo[y-1][x-1], memo[y-1][x], memo[y][x-1]) + 1 이다.

(c에서 min에 인자 3개들어가면 오류인것에 유의)

정리

내 코드 (ms)	빠른 코드 (ms)
12

고생한 점

map의 시작 index를 1부터 잡았으나, 한 줄 씩 읽은 line을 map으로 변환할 때 0부터 index를 잡아 오류가 발생함

code

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

using namespace std;

int memo[1001][1001] = { 0, };

void solution() {
	int N, M;

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		string line;
		cin >> line;

		for (int j = 1; j <= M; j++) {
			memo[i][j] = line[j - 1] - '0';
		}
	}

	int answer = 0;

	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= M; x++) {
			if (memo[y][x] != 1) {
				continue;
			}

			int left, up, leftup;

			left = memo[y][x - 1];
			up = memo[y - 1][x];
			leftup = memo[y - 1][x - 1];

			memo[y][x] = min(min(left, up), leftup) + 1;
			answer = max(memo[y][x], answer);
		}
	}

	cout << answer * answer << "\n";
}

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

	solution();

	return 0;
}