[백준] 1025 - 제곱수 찾기 (Java)

문제 파악

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

N, M 이 적은 점을 참고하면 모든 해에 대해 탐색하며 업데이트하는 방향으로 진행하였다.

풀이

행/열에 해당하는 row/col을 순환하며 arr[row][col]부터 시작하는 등차수열을 만들어 제곱근일 경우 최댓값을 업데이트해 준다.
또한 row, col을 시작으로 하는 등차수열을 만들어준다. 

이때, 등차는 [-8,8]을 선정해도 무리는 없을 듯 하나, 나 같은 경우 총 행/열 중 큰 값으로 진행했다.

등차는 열, 행에 개별로 적용하자
열에 해당하는 등차는 oc, 행에 해당하는 등차는 or로 선언하고 풀이했다.

그림으로 보자면 다음과 같을 것이다.

row,col의 offset

물론 등차에 해당하는 oc, or를 더했을 시 범위를 벗어나는지 체크해야 한다.
열 등차, 행 등차가 모두 0일 경우의 케이스는 하나를 선택하는 경우이기에 미리 처리하여 진행하지 않도록 한다.

등차수열 중간에도 현재까지의 수열이 제곱수인지 체크하여 값을 업데이트해주도록 하자.
(이 부분을 실수로 빠트려 시간을 좀 썼다😅)

코드

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

public class Main {
    static int answer;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int row = Integer.parseInt(input[0]);
        int col = Integer.parseInt(input[1]);

        arr = new int[row][col];
        for (int i = 0; i < row; i++) {
            String[] rowInput = br.readLine().split("");
            for (int j = 0; j < col; j++) {
                arr[i][j] = Integer.parseInt(rowInput[j]);
            }
        }

        answer = -1;
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (isSquare(arr[r][c])) { // 하나의 선택에 대해서도 체크
                    answer = Math.max(answer, arr[r][c]);
                }
                int max = Math.max(row, col);
                for (int ro = -max; ro <= max; ro++) {
                    for (int co = -max; co <= max; co++) {
                        if (ro == 0 && co == 0) {
                            continue;
                        }
                        updateSquareNum(r, c, ro, co);
                    }
                }
            }
        }
        System.out.println(answer);
    }

    static void updateSquareNum(int r, int c, int ro, int co) {
        int br = r + ro;
        int bc = c + co;
        if (bc < 0 || bc >= arr[0].length || br < 0 || br >= arr.length) {
            return;
        }
        long num = 0;
        int nr = r;
        int nc = c;
        while (nr >= 0 && nr < arr.length && nc >= 0 && nc < arr[0].length) {
            num = num * 10 + arr[nr][nc];
            if (isSquare(num)) {
                answer = Math.max(answer, (int) num);
            }
            nr += ro;
            nc += co;
        }
    }

    static boolean isSquare(long num) {
        if (num < 0) {
            return false;
        }
        long sqrt = (long) Math.sqrt(num);
        return sqrt * sqrt == num;
    }
}