백준 1051번: 숫자 정사각형 (C++)

https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

 

풀이

완전 탐색인 듯해서 시간복잡도를 계산해보니 50*50*50정도 밖에 나오지 않았다.

그냥 완전 탐색을 돌려주었다.

 

 

전체 코드

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

using namespace std;

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

	int N, M;
	int ans = 1;
	int board[51][51] = { 0, };
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++) board[i][j] = s[j] - '0';
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int k = 1; k < min(N, M); k++) {
				if (i + k >= N || j + k >= M) break;
				if (board[i][j] == board[i + k][j + k] && board[i][j] == board[i][j + k] && board[i][j] == board[i + k][j]) {
					ans = max(ans, k + 1);
				}
			}
		}
	}

	cout << ans * ans;
}