[Java] 백준 1025번: 제곱수 찾기

문제 링크

문제

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

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

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

입력

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

출력

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

제한

• 1 ≤ N, M ≤ 9
• 표에 적힌 숫자는 0보다 크거나 같고, 9보다 작거나 같다.
  
  

풀이

• 만들 수 있는 모든 수에 대해 완전제곱수인지 판별 후 가장 큰 수를 구한다.
• for 문을 통해 각 행과 열의 수에 맞춰 시작 지점 i, j를 선택 후, 등차수열의 공차는 di, dj로 선택한다.
• 공차만큼 더했을 때 범위에 포함된다면, 완전제곱수인지 판별하고 answer와 비교해서 더 큰 수를 저장한다. 그 다음 다시 같은 값을 더해 다음 수를 만든다.

답안

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

public class Main {
    static int N, M;
    static int[][] table;
    static int answer = -1;

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

        table = new int[N][M];

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

        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) {
                            continue;
                        }
                        
						// 초기값, 초기위치
                        int num = 0;
                        int newRow = i;
                        int newCol = j;

                        while (newRow >= 0 && newRow < N && newCol >= 0 && newCol < M) {
                            num = num * 10 + table[newRow][newCol];

                            if (isPerfectSquare(num)) {
                                answer = Math.max(answer, num);
                            }

                            newRow += di;
                            newCol += dj;
                        }
                    }
                }
            }
        }
        System.out.println(answer);
    }

    private static boolean isPerfectSquare(int num) {
        int sqrt = (int) Math.sqrt(num);
        return sqrt * sqrt == num;
    }
}