백준 1025 (제곱수 찾기) - java

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

1025번: 제곱수 찾기

문제

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

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

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

• 1 ≤ N, M ≤ 9

유형 : 수학 + 구현

 

접근

• 등차 수열이기 때문에 이전에 증가한 칸 만큼 증가해야 한다.( 좌표계를 기준으로 )
• 완전 제곱수를 판단할 수 있어야 한다.
  • Java의 경우 Math.sqrt() 함수를 활용한다.
  • 재밌는 특징중에 Math.sqrt()를 실행한 값과 해당 값을 int형으로 형변환한 값을 비교하여 같은 경우 완전제곱수로 판단할 수 있다.
• 증가 폭에 대해 고민을 해봐야 한다.
  • 행으로 2칸 , 열로 1칸 씩 모두 움직인다면 이러한 움직임도 등차 수열로 판단할 수 있다는 것이다.

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    static String[][] board;

    static int[] dx = {1,-1,0,0,1,1,-1,-1};
    static int[] dy = {0,0,-1,1,1,-1,1,-1};

    static int result  = -1;
    static boolean[][] v;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new String[n+1][m+1];
        v = new boolean[n+1][m+1];

        for(int i=1;i<=n;i++){
            String line = br.readLine();
            for(int j=1;j<=m;j++){
                board[i][j] = line.charAt(j-1)+"";
            }
        }

        int maxP = Math.max(n,m);

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(board[i][j].equals("0")){
                    result = Math.max(result,0);
                }

                else{
                        for(int ip = 1;ip<=maxP;ip++){
                            for(int jp = 1;jp<=maxP;jp++){
                                if(ip == 0 && jp == 0)
                                    continue;

                                for(int d=0;d<8;d++){
                                    travel(i,j,d,ip,jp,board[i][j]);
                                }
                            }
                        }
                    }
                }
        }

        System.out.println(result);
        br.close();
    }

    static void travel(int x,int y,int dir,int sx,int sy,String cur){
        cal(cur);

        int nx = x + (sx * dx[dir]);
        int ny = y + (sy * dy[dir]);

        if(nx < 1 || nx > n || ny < 1 || ny > m)
            return;

        travel(nx,ny,dir,sx,sy,cur+board[nx][ny]);
    }

    static void cal(String cur){
        int tmp = Integer.parseInt(cur);

        double tmpD = Math.sqrt(tmp);
        int tmpI = (int)tmpD;

        if(tmpD == tmpI){
            result = Math.max(result,tmp);
        }
    }
}