[BOJ] 백준 #1051. 숫자 정사각형 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/1051

• 알고리즘 분류: 구현, 브루트포스
• 난이도: Silver 3

 

💬 풀이

또 은근 구현이 까다로웠던 문제

1. 한 글자씩 입력받기 ― scanf() 사용
2. 닥치고 이중for문 돌리기
   • N==1 or M==1이면 그냥 1. 끝.
   • arr[i][j]가 ‘정사각형의 왼쪽 위 꼭짓점’이라 생각하고 탐색 시작
   • 가장 큰 걸 구하는 거니까 1부터 돌지말고 큰 것부터 ㅇㅇ. for (int k = min(N-i-1, M-j-1); k>0; k--)
   • if (k < l) break; : 예를 들어 l=3인데 탐색 남은 줄이 2줄 밖에 없다면 할 필요 없음.

 

‘문자열 입력받는 여러 가지 방법 총정리’를 해야겠다. (언젠가)
입력 방법에 대해 매번 정확하게 알고 있는 것 같지 않으니 그때그때 정리할 필요가 있겠다.

 

 

 

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	int N, M;
	cin >> N >> M;
	int** arr = new int* [N];
	for (int i = 0; i < N; i++) {
		arr[i] = new int[M];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}

	// arr[i][j]가 정사각형 왼쪽 위 꼭짓점이라고 치고 브루트포스
	int l = 1;
	if (N == 1 || M == 1) {
		cout << 1;
		return 0;
	}
	else {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				for (int k = min(N - i - 1, M - j - 1); k > 0; k--) {
					if (k < l) break;
					if (arr[i][j] == arr[i][j + k]
						&& arr[i][j] == arr[i + k][j]
						&& arr[i][j] == arr[i + k][j + k]) {
						l = max(k + 1, l);
						break;
					}
				}
			}
		}
	}
	cout << l * l;

	return 0;
}