[백준 01025] 제곱수 찾기 [Java]

문제

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

 

---

풀이

N*M 의 보드에서 행과 열이 등차수열을 이루는 칸들의 숫자를 이어 붙여 만든 수가, 어떤 정수의 제곱수 중 가장 큰 제곱수를 찾는 문제다.

만약 찾지 못했다면 -1을 반환해야 한다.

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

행과 열에 대한 등차수열이기 때문에 각 위치에 2N * 2M 범위에 대한 등차수열을 찾으면 된다.

                for (int dx = -N; dx < N; ++dx) {
                    for (int dy = -M; dy < M; ++dy) {

만약 증가값이 둘 다 0이라면 탐색이 불가능하므로 유의하며, 숫자를 이어 붙인 후 가장 큰 제곱수를 찾아주면 된다.

                        if (dx != 0 || dy != 0) {
                            int x = i;
                            int y = j;
                            int num = 0;
                            while (x >= 0 && x < N && y >= 0 && y < M) {
                                num = num * 10 + A[x][y];
                                if (isSquare(num)) {
                                    res = Math.max(res, num);
                                }
                                x += dx;
                                y += dy;
                            }
                        }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01025.java