[백준] 1025 제곱수 찾기 java

문제

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

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

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

입력

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

출력

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

제한

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

풀이

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int n, m, max;
    static int[][] board;

    public static void main(String[] args) throws IOException {
        init();
        solve();
        System.out.println(max == Integer.MIN_VALUE ? -1 : max);
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        board = new int[n][m];
        max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < m; j++) {
                board[i][j] = str.charAt(j)-'0';
            }
        }
    }

    static void solve() {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    for(int x = -n; x < n; x++) {
                        for(int y = -m; y < m; y++) {
                            if(x == 0 && y == 0) continue;
                            StringBuilder val = new StringBuilder();
                            int a = i;
                            int b = j;
                            while(a >= 0 && b >= 0 && a < n && b < m) {
                                if(isSquareNum(board[a][b])) {
                                    max = Math.max(max, board[a][b]);
                                }
                                val.append(board[a][b]);
                                if(isSquareNum(stoi(val.toString()))) {
                                    max = Math.max(max, stoi(val.toString()));
                                }
                                a = a + x;
                                b = b + y;
                            }
                        }
                    }
                }
            }
    }

    static boolean isSquareNum(int n) {
        int root = (int)Math.sqrt(n);
        if(root*root == n) {
            return true;
        }
        return false;
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

무려 4중(?)for문을 사용한 완전탐색 문제였다.

 

처음에 문제를 읽고 잘 이해하지 못해 문제 접근 조차 할 수 없어 다른 분들의 코드를 봤다 ㅜ

 

이 문제는 1개 이상의 선택된 정수들의 위치의 행, 열이 각각 등차수열이 되어야 하고 이렇게 선택된 정수들을 이어붙힌 값이 제곱수가 되는 값들 중 최댓값을 찾으면 되는 문제이다. 그렇다면 해결해야 할것은 2가지로 추려진다.

 

1. 모든 행, 열에 대해서 모든 공차별로 모든 길이의 값들을 비교해야 한다. (이 경우 n, m 값이 작기 때문에 브루트포스 가능)

 

2. 구해진 값이 제곱수를 만족하는 수 인지 판별

 

1번이 무슨 뜻인고 하면 예를 들어보자.

 

ex) (0, 3) (0, 4) (0, 5) => 열의 공차가 1인 등차수열을 만족

      (0, 3) (0, 5) (0, 7) => 열의 공차가 2인 등차수열을 만족

      (0, 3) (0, 2) (0, 1) => 열의 공차가 -1인 등차수열을 만족

      

이런 식으로 총 -n ~ n 까지의 공차 그리고 -m ~ m 까지의 공차를 모두 구해야 한다.

 

그리고 각 공차별로 구할 수 있는 모든 값들을 비교해야 하는데 중요한건 각 자리마다 매번 검사를 따로 해주어야 한다. 

 

두번 째로 제곱수인지 만족하는 수를 판별하는 것은 해당 수 n의 루트값을 구해서 그 루트값 * 루트값이 n과 같다면 제곱수이다.