[백준 알고리즘] 1025번 : 제곱수 찾기 (JAVA) 문제 풀이

문제

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

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

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

입력

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

출력

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

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

1025번: 제곱수 찾기

 

문제 풀이 : 

우선은 처음에 문제를 파악하는 것이 어려운 문제였다.

행과 열이 등차수열을 이루어야 한다.

행과 열의 등차수열에 따라 값을 이루는 것이 제곱수여야한다.

근데 그 값들 중에 최대값이여야 한다.

즉, 브루트포스(완전탐색) 알고리즘이다.

다만, DFS나 BFS를 이용한 완전탐색이 아닌, for문과 while을 이용한 완전탐색이였다.

 

문제의 예를 들면,

 

2 3

123

456

 

이렇게 문제가 주어졌을 때,

 

(1,3) (2,3)은 등차수열을 이룬다.

해당 순서로 수를 뽑아내면 36이 된다.

정답

 

(1,1) (1,2) (1,1)로 수를 뽑으면 121로 11의 제곱수이지만,

등차수열이 아니다.

오답

 

따라서 위에서 해당 조건을 모두 만족하는 최대의 수를 뽑아내면 결국에는 64가 된다.

(2,3) (2,1)

 

 

내 코드 : 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static int[][] array;
	static String[] arr;
	static int answer = -1;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new String[N + 1];
		array = new int[N][M];

		for (int i = 0; i < N; ++i) {
			arr[i] = br.readLine();
			for (int j = 0; j < M; ++j) {
				array[i][j] = arr[i].charAt(j) - '0';
			}
		}

		for (int i = 0; i < N; ++i) { 
			for (int j = 0; j < M; ++j) { 

				solve(j, i);
			}
		}

		System.out.println(answer);

	}

	public static void solve(int c, int r) {
		for (int i = -N; i < N; ++i) { 
			for (int j = -M; j < M; ++j) {

				if (i == 0 && j == 0)
					continue;

				int x = c; 
				int y = r; 

				int sqr = 0;

				while (0 <= x && x < M && 0 <= y && y < N) {
					sqr *= 10;
					sqr += array[y][x];

					int root = (int) Math.sqrt(sqr);

					if (Math.pow(root, 2) == sqr)
						answer = Math.max(answer, sqr);

					x += j;
					y += i;
				}
			}
		}
	}

}