[백준 JAVA] 1025. 제곱수 찾기

문제 링크

---

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

접근 방법

---

이 문제는 모든 시작 위치에서, 모든 방향과 간격으로 이동하면서 만들 수 있는 수를 전부 확인해야 합니다.

시작 좌표를 (i, j)로 정하고, 행 변화량 dy, 열 변화량 dx를 정한 뒤 현재 위치의 숫자를 이어 붙여 하나의 수를 만듭니다.

이때 dy, dx는 음수, 양수, 0 모두 가능하며, (0, 0)은 제외해야 합니다.

숫자를 한 자리씩 이어 붙일 때마다 매번 완전 제곱수인지 확인해야 합니다.

소스 코드

---

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

public class Main {

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

        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][m];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < s.length(); j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }

        long ans = -1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int dy = -n; dy < n; dy++) {
                    for (int dx = -m; dx < m; dx++) {
                        if (dy == 0 && dx == 0) {
                            continue;
                        }

                        int curY = i, curX = j;
                        long num = 0;

                        while (curY >= 0 && curX >= 0 && curY < n && curX < m) {
                            num = num * 10 + arr[curY][curX];

                            long tmp = (long) Math.sqrt(num);
                            if (tmp * tmp == num) {
                                ans = Math.max(ans, num);
                            }

                            curY += dy;
                            curX += dx;
                        }
                    }
                }
            }
        }

        System.out.println(ans);
    }
}

코드 설명

---

i, j는 숫자를 만들기 시작하는 시작 좌표입니다.

dy, dx는 다음 칸으로 이동할 때의 행, 열 변화량입니다.
예를 들어 (1, 1)이면 오른쪽 아래 대각선으로 한 칸씩 이동하고, (0, 2)이면 같은 행에서 두 칸씩 이동합니다.

(dy, dx) = (0, 0)이면 제자리만 반복하게 되므로 제외해야 합니다.
num = num * 10 + arr[curY][curX]를 통해 이전 숫자의 뒤에 현재 칸의 숫자를 붙일 수 있습니다.

숫자를 만들 때마다 Math.sqrt(num)으로 제곱근을 구하고, 다시 제곱했을 때 원래 수와 같으면 완전 제곱수입니다.

모든 시작점과 모든 이동 방향을 확인한 뒤, 완전 제곱수를 한 번도 만들지 못했다면 초기값 -1이 그대로 출력됩니다.