백준 - 제곱수 찾기

문제 설명

N행 M열의 배열이 주어지고 서로 다른 2개 이상의 칸은 선택하여 만들 수 있는 수중 가장 큰 완전 제곱수를 구하는 문제이다.

서로 다른 2개 이상의 칸을 선택하기 위해서는 행의 번호가 순서대로 등차 수열을 이루고 있어햐 하고 열의 번호도 선택한 순서대로 등차 수열을 이루고 있어야 한다.

주의사항

서로 다른 2개 이상의 칸을 탐색하기 위한 문제 이해가 중요하다.

행의 번호가 순서대로 등차 수열을 이루고 있어야 한다. 열의 번호도 동일하다.

나는 처음에 값이 등차수열을 이루어야 한다고 착각했다. 그것이 아니라 인덱스 간격이 등차수열을 이루어야 한다는 이야기이다.

즉 행에 대해 +2칸 이면 (0,0) → (2,0) → (4,0) → (n-2,0) 까지 등차수열의 간격을 이루고 탐색한 칸의 값을 모두 이어붙여 정수를 추출하고 해당 정수가 완접 제곱수가 되는지 판별해야 하는 문제이다.

또다른 예시로 행에 대해 2칸 열의 대해 2칸 간격의 등차수열 간격을 이루고 탐색한 칸은 이렇게 된다.

(0,0) → (2,2) → (4,4) → (n-2, m-2) 가 되어 행에 대해 2칸의 간격, 열의 대해 2칸의 간격이 된다.

풀이

---

  static int n, m;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(reader.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		int map[][] = new int[n][m];
		for (int i = 0; i < n; i++) {
			String[] split = reader.readLine().split("");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(split[j]);
			}
		}
		int answer = getAnswer(map);
		/**
		 * 문제 이해 중요 및 구현능력 (등차수열이루고 있는
		 */

		System.out.println(answer);
	}

	public static int getAnswer(int[][] arr) {
		int answer = -1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {

				// 등차 수열 간격 (행열에대해서)
				for (int di = -n; di < n; di++) { // 행의 등차 간격
					for (int dj = -m; dj < m; dj++) { // 열의 등차 간격
						if (di == 0 && dj == 0) {
							// 등차수열 간격이 모두 0이면 움직이지 않는다.
							continue;
						}

						String numbers = "";
						int ny = i;
						int nx = j;

						while (!isOutOfRange(ny, nx)) {
							numbers += String.valueOf(arr[ny][nx]);

							if (isSquare(numbers)) { // 제곱수인가?
								answer = Math.max(answer, Integer.parseInt(numbers));
							}

							ny += di;
							nx += dj;
						}
					}

				}
			}
		}

		return answer;
	}
	// 0.000000001도 존재하면 안됀다. 그래야 제곱수
	private static boolean isSquare(String numbers) {
		int number = Integer.parseInt(numbers);

		return Math.abs(Math.sqrt(number) - (int)Math.sqrt(number)) == 0;
	}

	public static boolean isOutOfRange(int ny, int nx) {
		return ny < 0 || nx < 0 || ny >= n || nx >= m;
	}