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

 

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

1025번: 제곱수 찾기

 

 

행과 열이 등차수열을 이루어야 한다.

 

예를 들면,

 

2 3

123

456

 

이렇게 수가 있을 때,

 

1번

(1,1) (1,2) (1,3)는 등차수열을 이룬다.

해당 순서로 수를 뽑아내면 123이 된다.

하지만 123은 제곱수가 될 수 없다.

탈락

 

 

2번

(1,3) (2,3)은 등차수열을 이룬다.

해당 순서로 수를 뽑아내면 36이 된다.

합격

 

 

3번

(1,1) (1,2) (1,1)로 수를 뽑으면 121로 11의 제곱수이지만,

등차수열이 아니다.

탈락

 

 

따라서 위에서 해당 조건을 모두 만족하는 최대의 수를 뽑아내면 결국에는 64가 된다.

(2,3) (2,1)

 

 

 

문제 설명이 좀 이해하기 어려운데,

 

수정 이후인 지금도 껄끄러운 면이 있다.

 

결국 다중 반복문을 사용하게 하는 문제 자체가 좀 난해한 느낌도 있다.

 

 

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

public class Main {
    // 입력 배열
    static String[] arr;
    static int[][] map;

    static int N, M;
    static int ans = -1;

    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());

        arr = new String[N+1];
        map = new int[N][M];

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


        // 다중 반복문은 연산 과정이 좀 헷갈리니 나눔
        for(int i=0; i<N; ++i){ // 행 시작 부분 제한
            for(int j=0; j<M; ++j){ // 열 시작 부분 제한

                // 제한된 범위인 i x j를 파라미터로 메서드 호출
                slv(j, i);
            }
        }

        System.out.println(ans);

    }

    public static void slv(int c, int r){
        for(int i=-N; i<N; ++i){ // 행 공차
            for(int j=-M; j<M; ++j){ // 열 공차

                // 연두는 서로 다른 1개 이상의 칸을 선택 --> (1,1), (1,1)과 같은 경우는 무시
                if(i == 0 && j == 0) continue;

                int x = c; // 제한된 열 시작 부분
                int y = r; // 제한된 행 시작 부분

                // 만들어질 제곱수
                int sqr = 0;

                // 범위 체크
                while (0<=x && x<M && 0<=y && y<N){
                    // 제곱수 생성
                    sqr *= 10;
                    sqr += map[y][x];

                    // 제곱근 구하기
                    int root = (int)Math.sqrt(sqr);

                    // 제곱수 판별
                    if( Math.pow(root, 2) == sqr )
                        ans = Math.max(ans, sqr);

                    x += j;
                    y += i;
                }
            }
        }
    }

}

 

시작하는 행, 열 부분을 정한 후 (main의 첫 2중 for문)

 

증감하는 공차에 따라 (slv 메서드 내의 2중 for문)

 

제곱수를 생성하고, (공차를 이용해 while문 내에서 범위의(음 또는 양) 끝까지 이동하며 제곱수의 자릿수를 하나씩 추가)

 

제곱수를 판별한 후 최댓값인지 확인한다.