[백준알고리즘] 1025번: 제곱수 찾기 -C++

[백준알고리즘] 1025번: 제곱수 찾기 -C++

1025번: 제곱수 찾기 (acmicpc.net)

1025번: 제곱수 찾기

이번 문제는 생각보다 불친절하다. 입력의 범위(n, m)라던가 출력의 범위 등 구체적으로 정해진 것이 없다. 그래서 어쩔 수 없이 브루트 포스를 이용했는데 그것 마저도 범위가 주어지지 않으니 자료형에서 불편함이 있었다.

 

문제 자체도 불친절해서 문제에 대한 설명도 같이 하겠다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제 설명

문제 설명이 지문에 굉장히 불친절해서 질문 게시판에서도 계속해서 지문 변경을 요청한다... 심지어 백준님도 이해 안 된다고 답글 다신 ㅋㅋㅋㅋ

 

문제에서 요구하는 것을 다시 정리해보도록 하자.

1. \(N \times M\) 크기의 격자판에 수를 채워 넣는다. 
2. 이때 \(x\)축과 \(y\) 축 모두 등차를 이루는 수들을 수열로 만든다.
3. 만들어진 수열의 수를 붙여서 출력한다.

 

예를 들어보도록 하자.

격자판에 다음과 같은 수가 주어져있다고 생각해보자.

1	2	3	4
5	6	7	8
9	0	1	2
3	4	5	6

 

여기서 (0, 0)을 좌측 상단의 1로, (3, 3)을 우측 하단의 6으로 생각을 해보자.

 

그렇다면, 제곱수를 고려하지 않고 가능한 수열은 수없이 많지만, 다음과 같은 경우도 포함이 된다.

 

\(\{(0, 0)\}, \\ \{(0, 0), (0, 2)\}, \\ \{(3, 3), (1, 1)\}, \\ \{(1, 2), (0, 0)\}, \\ \{(3, 3), (2,2), (1,1)\} \\ ...... \)

 

위에서부터 각각 \(x\)축과 \(y\) 축에 대한 공차를 다루면 다음과 같다.

 

\((0, 0), \\ (0, 2) \\ (2, 2) \\ (-1, -2) \\ (-1, -1) \)

 

따라서 이렇게 x축과 y축 모두 등차를 이루는 셀들을 선택해 수열을 만드는 것을 요구하는 문제다. 여기서, 만들어진 수 중 제곱수를 찾으면 된다.

 

 

풀이 방법

우선 문제를 푸는 과정은 위의 설명에서와 같이 풀면 된다. 나눠서 생각해보면 아래와 같다.

1. 각 셀의 \(x\)축과 \(y\) 축이 등차를 이루는 수열을 찾아낸다.
2. 수열을 하나의 수로 만든다.
3. 해당 수가 제곱수인지 판단한다.

 

1번과 2번 과정을 해결하기 위해서 findSquare 함수를 구현했다. findSquare 함수에서는 공차를 먼저 지정하고, 해당 공차로 만들 수 있는 수열을 만드는 방식을 선택했다.

 

3번 과정을 위해서 isSquare 함수를 따로 구현했다. 이 경우에는 해당 수의 제곱근을 int형으로 변환한 뒤, 그 값을 제곱하면 원래의 수가 나오는지로 해당 수가 제곱수가 맞는지 확인했다. 제곱수의 경우 제곱근이 0 이상의 정수가 나올 것이고, 그 수를 제곱하면 원래의 수가 나오기 때문이다. 제곱수가 아니라면, 제곱근은 정수가 아닌 실수가 나온다.

 

---

 

아래는 위의 풀이 방밥으로 푼 C++ 코드다.

입력이 얼마나 주어질지 궁금해서 findSquare 반복문들의 중간에 비효율적인 부분이 있지만, 0ms로 통과한 것을 보면 입력의 크기가 굉장히 큰 것은 없는 것 같기도 하다.

#include <iostream>
#include <vector>
#include <cmath>

int64_t n, m;

void solve(void);

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

	solve();
}

bool isSquare(const int64_t num)
{
	int64_t squareRoot = sqrt(num);
	return (squareRoot * squareRoot == num);
}

int64_t findSquare(const std::vector<std::vector<int>>& board, const int64_t i, const int64_t j)
{ 
	int64_t square = -1;

	for (int64_t dy = -n + 1; dy < n; dy++)
	{
		for (int64_t dx = -m + 1; dx < m; dx++)
		{
			if (dy == 0 && dx == 0)
			{
				if (isSquare(board[i][j]) && square < board[i][j])
					square = board[i][j];
				continue;
			}

			int64_t ty = i + dy;
			int64_t tx = j + dx;
			if (ty < 0 || n <= ty || tx < 0 || m <= tx)
				continue;

			int64_t curr = board[i][j];

			while (0 <= ty && ty < n && 0 <= tx && tx < m)
			{
				curr = curr * 10 + board[ty][tx];

				if (isSquare(curr) && square < curr)
					square = curr;

				ty += dy;
				tx += dx;
			}
		}
	}

	return square;
}

void solve(void)
{
	std::cin >> n >> m;

	int64_t line;
	std::vector<std::vector<int>> board(n, std::vector<int> (m));
	for (int64_t i = 0; i < n; i++)
	{
		std::cin >> line;
		for (int64_t j = m - 1; 0 <= j; j--)
		{
			board[i][j] = line % 10;
			line /= 10;
		}
	}
	
	int64_t answer = -1;
	for (int64_t i = 0; i < n; i++)
		for (int64_t j = 0; j < m; j++)
		{
			int64_t squareNumber = findSquare(board, i, j);
			answer = (answer < squareNumber ? squareNumber : answer);
		}

	std::cout << answer;
}