1051번: 숫자 정사각형
N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.
www.acmicpc.net
깊게 생각하지 않고 단순하게 접근하면 쉽게 풀리는 문제라 생각한다.
map[0][0]을 기준으로 검사할 때를 예로 들어보자면 map[0][0], map[0+k][0], map[0][0+k] 세 값이 일치할 때
즉, 세 꼭짓점의 숫자가 같다면 마지막 꼭짓점인 map[0+k][0+k]과 map[0][0] 값이 일치하는지 검사한다.
일치한다면 조건을 만족하는 정사각형이 되므로 k는 정사각형 한 변의 길이가 된다.
문제 예제에서 k = 2일 때 정사각형 넓이가 9로 출력되었으니 정사각형의 넓이는 (k+1)^2라는 것을 알 수 있다.
따라서 map[0][0] ~ map[n-1][n-1] 까지 모든 원소를 다 탐색하면서 조건을 만족하는 정사각형이 만들어질 때 그 넓이가 가장 큰 값을 갱신해주면 원하는 결과를 얻을 수 있다.
|
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> board;
int colMax, rowMax;
int MaxSquare = 1;
int max(int a, int b) { return a > b ? a : b; }
void Solution()
{
for (int i = 0; i < colMax; i++)
for (int j = 0; j < rowMax; j++)
for (int k = 1; k < colMax; k++)
if (i + k < colMax && j + k < rowMax)
if (board[i][j] == board[i + k][j] && board[i][j] == board[i][j + k])
if (board[i][j] == board[i + k][j + k])
MaxSquare = max(MaxSquare, (k+1)*(k+1));
}
int main(void)
{
cin >> colMax >> rowMax;
for (int i = 0; i < colMax; i++)
{
string str;
cin >> str;
board.push_back(str);
}
Solution();
cout << MaxSquare << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 19day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 7453번: 합이 0인 네 정수 (0) | 2020.04.26 |
|---|---|
| 백준 1038번: 감소하는 수 (0) | 2020.04.25 |
| 백준 3085번: 사탕 게임 (c++) (0) | 2020.04.24 |
| 백준 2503번: 숫자 야구 (c++) (0) | 2020.04.23 |
| 백준 15684번: 사다리 조작 (c++) (0) | 2020.04.22 |