백준 1025 [자바] java 제곱수 찾기
2022.01.12 11:52
Alogorithm/Brute Force
문제 링크: https://www.acmicpc.net/problem/1025
1025번: 제곱수 찾기
첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어진다.
▶문제
N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.
연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.
연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.
▶입력
첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.
▶출력
첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.
▶해설
행과 열의 인덱스가 등차수열을 이룬다는 조건을 만족하며 완전 제곱수를 찾아가는 문제입니다. 총 6가지의 유형이 나올 수 있습니다.
1. 왼쪽 아래에서 위로 올라가는 형태
2. 왼쪽 위에서 아래로 내려가는 형태
3. 오른쪽 아래에서 위로 올라가는 형태
4. 오른쪽 위에서 아래로 내려가는 형태
5. 행만 움직이는 형태
6. 열만 움직이는 형태
6가지의 유형을 모두 만족하는 코드를 작성하면 됩니다. 모든 수를 탐색해야 하므로 브루트포스 방식으로 진행하면됩니다. 별도의 설명은 주석으로 하겠습니다.
행과 열이 등차수열을 이루어야 한다.
예를 들면,
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의 제곱수이지만,
등차수열이 아니다.
탈락
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 제곱수찾기 {
static int n, m;
static int[][] arr;
static int result = -1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
arr = new int[10][10];
for (int i = 0; i < n; i++) {
String s1 = br.readLine();
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(String.valueOf(s1.charAt(j)));
}
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
for (int mi = -n; mi < n; ++mi)
for (int mj = -m; mj < m; ++mj) {
if (mi == 0 && mj == 0) { // 둘다 움직이지 않을 때
continue;
}
int t = 0;
int newI = i;
int newJ = j;
while (newI >= 0 && newI < n && newJ >= 0 && newJ < m) // 위치가 0>= && <범위를 설정해줍니다.
{
t = 10 * t + arr[newI][newJ]; // 기존에 담긴 숫자가 있다면 *10해주고 더해줍니다.
if (Math.abs(Math.sqrt(t) - (int) Math.sqrt(t)) < 1e-10) { // 완전 제곱수인지 판별합니다.
result = Math.max(result, t);
}
newI += mi;
newJ += mj;
}
}
System.out.println(result);
}
}