[백준 1025] 제곱수 찾기 (C++)

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

문제

---

N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.

연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.

연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.

 

입력

---

첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.

출력

---

첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.

 

제한

---

• 1 ≤ N, M ≤ 9
• 표에 적힌 숫자는 0보다 크거나 같고, 9보다 작거나 같다.

문제 풀이

---

브루트포스 문제.

 

행과 열의 번호가 순서대로 등차수열을 이루고 있어야 한다. 따라서 시작 지점의 행과 열, 행의 공차, 열의 공차를 반복문으로 정한 후, 해당 위치로 얻어지는 숫자가 완전 제곱수인지 확인해주면 된다. 표를 벗어날 때까지 문자열에 해당 칸의 숫자를 덧붙여 최종 숫자를 만드는데, 서로 다른 칸을 선택해야 하므로 이미 선택한 칸을 다시 선택한다면 return으로 계산되지 못하게 한다.

이렇게 만들어진 최종 숫자는 배열이 시작 지점, 행과 열의 공차가 허락하는 최대 길이이다. 즉, 예를 들어 최종 숫자로 4900이 얻어졌을 경우, 완전 제곱수에 해당하는 첫 2문자인 49에 대해서는 계산되지 않고 4900에 대해서만 값이 구해진다. 따라서 substr를 이용하여 4, 49, 490, 4900 등 모든 길이에 대해 완전 제곱수인지 판별해주어야 한다.

 

4중 for문이지만, N과 M이 최대 9까지이기 때문에 시간초과가 발생하지 않는다. 

 

아래는 코드.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
char** arr;
bool** isVisited;

int N, M;
int answer = -1;

void find(int startRow, int startCol, int rowD, int colD)
{
	string str = "";
	int i = startRow;
	int j = startCol;
	while (true)
	{
		if (i >= 0 && i < N && j >= 0 && j < M)
		{
			if (isVisited[i][j] == false)
			{
				str += arr[i][j];
				isVisited[i][j] = true;
				i += rowD;
				j += colD;
			}
			else
			{
				return;
			}
		}
		else
		{
			break;
		}
	}
	for (int i = 1; i <= str.length(); i++)
	{
		int num = stoi(str.substr(0, i));
		int sqrtNum = sqrt(num);
		if (sqrtNum * sqrtNum == num)
		{
			answer = max(answer, num);
		}
	}
}

void reset()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			isVisited[i][j] = false;
		}
	}
}

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

	cin >> N >> M;
	arr = new char* [N];
	isVisited = new bool*[N];
	for (int i = 0; i < N; i++)
	{
		isVisited[i] = new bool[M];
		arr[i] = new char[M];
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
			isVisited[i][j] = false;
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			for (int rowD = -N; rowD <= N; rowD++)
			{
				for (int colD = -M; colD <= M; colD++)
				{
					reset();
					find(i, j, rowD, colD);
				}
			}
		}
	}
	cout << answer << "\n";
	return 0;
}