문제
N x M 표에서 행 인덱스와 열 인덱스가 각각 등차수열을 이루는 칸들을 선택하여 순서대로 이어붙인 수 중 가장 큰 완전 제곱수를 구하라. 없으면 -1을 출력.
입력
첫째 줄에 N, M (1 ≤ N, M ≤ 9), 이후 N줄에 M자리 숫자가 공백 없이 주어진다.
출력
가장 큰 완전 제곱수를 출력한다. 없으면 -1.
예제
| 입력 | 출력 |
|---|---|
2 3 123 456 | 64 |
풀이
모든 시작점과 등차(방향)에 대해 숫자를 이어붙여 완전 제곱수를 판별한다.
- 모든 시작점 (i, j)를 순회한다
- 각 시작점에서 가능한 모든 방향 (dr, dc)를 설정한다 (dr, dc는 다른 점으로의 증분)
- 방향이 (0, 0)인 경우(제자리)는 제외한다
- 해당 방향으로 진행하며 숫자를 이어붙이고(
num = 10 * num + digit), 매 단계 제곱수 여부를 확인한다 - 제곱수이면 최댓값을 갱신한다. 한 자리 숫자(시작점 자체)도 별도로 검사한다
핵심 아이디어: N, M이 9 이하로 작아 가능한 모든 등차수열 조합(O(N^2 * M^2 * max(N,M)))을 브루트포스로 탐색해도 시간 내에 해결된다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day198BOJ1025제곱수찾기 {
private static int n;
private static int m;
private static int[][] table;
private static int max = -1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
n = input.charAt(0) - '0';
m = input.charAt(2) - '0';
table = new int[n][m];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < m; j++) {
table[i][j] = str.charAt(j) - '0';
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
checkSquare(table[i][j]);
makeNum(i, j);
}
}
System.out.print(max);
br.close();
}
private static void makeNum(int row, int col) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 방향 설정
int dr = i - row;
int dc = j - col;
if (dr == 0 && dc == 0)
continue;
appendNum(row + dr, col + dc, dr, dc, table[row][col]);
}
}
}
private static void appendNum(int row, int col, int dr, int dc, int num) {
if (row < 0 || row >= n || col < 0 || col >= m)
return;
int newNum = 10 * num + table[row][col];
checkSquare(newNum);
appendNum(row + dr, col + dc, dr, dc, newNum);
}
private static void checkSquare(int num) {
int sqrt = (int) Math.sqrt(num);
if (sqrt * sqrt == num && num > max)
max = num;
}
}복잡도
- 시간: O(N² * M² * max(N, M))
- 공간: O(N * M)