문제 링크 : https://www.acmicpc.net/problem/1025
문제
N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.
연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.
연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.
입력
첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.
출력
첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.
포인트
- brute force
N과 M의 크기가 큰 편이 아니므로 전체 탐색을 진행해도 시간이 그렇게 오래 걸리진 않는다.
- 규칙성 찾기
숫자가 만들어지는 경우는 아래와 같다.
-
행 또는 열로만 이루어지는 경우
-
좌상단으로 이동
-
좌하단으로 이동
-
우상단으로 이동
-
우하단으로 이동
여기서 행공차(rd)와 열공차(cd)의 기준으로 살펴보면 아래와 같다.
-
행으로만 이루어지는 경우 -> cd == 0
-
열로만 이루어지는 경우 -> rd == 0
-
좌상단으로 이동 -> cd < 0 && rd < 0
-
좌하단으로 이동 -> cd < 0 && rd > 0
-
우상단으로 이동 -> cd > 0 && rd < 0
-
우하단으로 이동 -> cd > 0 && rd > 0
처음에는 각각의 경우를 나누어 조건을 구하다가 규칙성이 발견되어 합칠 수 있겠다는 생각이 들었다.
행공차의 범위는 -N~N이고 열공차의 범위는 -M~M이기 때문에 for을 활용하여 공차의 범위를 모두 조정할 수 있다.
- 제곱수 체크
제곱수를 체크할 때 Math.sqrt 함수를 사용했다. 이는 제곱근으로 만들어주는 함수인데 완전 제곱 수의 경우 제곱근으로 바꾸면 정수가 나와야 한다.
따라서 제곱근을 구하고 1로 나누었을 때 나머지가 0이 나오지 않는다면 그것은 제곱 수가 아니다. (자바에서는 double형 % 1을 하는 경우 그 소수부분이 출력된다.)
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_1025_제곱수찾기 {
static int N, M;
static char[][] map;
static int ans;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 입력 값 추가
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
ans = -1;
map = new char[N+1][M+1];
for (int i=1;i<=N;i++){
char[] c = br.readLine().toCharArray();
if (M >= 0) System.arraycopy(c, 0, map[i], 1, M);
}
// 만들 수 있는 자리 경우의 수
// 1. 행 또는 열로만 이루어진 형태
// 2. 좌상단으로 이동
// 3. 좌하단으로 이동
// 4. 우상단으로 이동
// 5. 우하단으로 이동
// 만들다보니 규칙성 발견
checkMap();
System.out.println(ans);
}
static void checkMap(){
for (int i=1;i<=N;i++){
for (int j=1;j<=M;j++){
for (int rd=-N; rd<=N;rd++){
for(int cd=-M;cd<=M;cd++){
// 행공차(rd)와 열공차(cd)의 범위는 -N~N과 -M~M이다.
// 좌상단 좌하단 우상단 우하단은 이와 같은 범위에서 각각이 -인가 +인가에 따라 좌표가 달라지므로 합치기 가능
// 기준 점 생성
int ny = i;
int nx = j;
// 둘다 0인 경우 움직이지 않음
if(rd == 0 && cd == 0) continue;
StringBuilder sb = new StringBuilder();
while (ny >= 1 && ny <= N && nx >= 1 && nx <= M){
sb.append(map[ny][nx]);
if(checkSqrt(sb.toString())) ans = Math.max(ans, Integer.parseInt(sb.toString()));
ny += rd;
nx += cd;
}
}
}
}
}
}
static boolean checkSqrt(String str){
int n = Integer.parseInt(str);
if(Math.sqrt(n)%1 == 0) return true;
else return false;
}
}
소감
엄청난 노가다를 반복하고 있었으나 규칙성을 찾고보니 간단하게 해결되는 모습을 볼 때마다 아직 많이 부족함을 느낀다...
또한 공차가 멈추는(?) 경우도 있다.
기존에는 범위 내의 모든 숫자를 넣어 제곱수 체크를 진행하였으나 계속해서 틀렸었다. 그래서 정답 코드를 참고하던 중 다른 코드에서는 숫자를 추가함과 동시에 제곱수 체크를 진행하는 방식으로 구현하길래 적용해보았더니 한번에 맞았다...
생각해보니 등차 수열을 이루고 있어야 한다고 했지 그 등차 수열이 무한이라는 말은 안했는데... 생각을 못했다. 문제를 제대로 이해해야 할 것 같다.
