[BOJ 1025] 제곱수 찾기

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

본문

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

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
2sec	128MB

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

---

풀이

문제 설명부터 이해해보자.

표 상에서 몇개의 칸을 선택할 것인데, 선택한 칸들은 행과 열이 모두 등차수열을 이루어야한다. 즉, 선택한 칸들을 나열할 때 행의 번호가 등차수열 + 열의 번호가 등차수열이어야하고, 그 순서는 바꾸지 않고 차례대로 적어 수를 하나 만들려고 한다. 그런 수들이 여러개 나올텐데, 문제에서 원하는 답은 그 수들 중 제곱수들 중 최댓값이다.

제곱수임을 판별하는 방법은 그 정수의 정수 제곱근을 구하고, 그의 제곱이 원래 정수와 같은지를 비교한다.

그럼 표 상에서 행과 열이 모두 등차수열인 방법으로 수들을 선택할 수 있는지를 알아보아야한다. 근데 그런건 없다. 다행히 표의 크기가 9칸이니 모든 방법에 대해서 찾아보는 브루트포스 알고리즘을 취할 수 있을 것이다. 반복문을 통해 모든 경우를 찾아보자.

한가지 고려해야할 것이 있는데, 칸들을 선택하여 수들을 만드는데 최종 완성된 수만 검사하면 안된다는 점을 알아야한다. 아직 표의 끝에 도달하지 않았음에도 선택한 수들을 이용하여 제곱수를 만들 수 있고, 그들 중 정답이 존재할 수 있기 때문이다. 칸을 선택하여 수를 만들 때마다 제곱수인지 판별하는 과정을 넣어주도록 하자.

소스코드

Github Link : Source Code

참고 알고리즘 : 브루트포스 알고리즘