| 시간 제한 | 메모리 제한 |
| 2초 | 128MB |
문제
N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.
연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.
연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.
입력
첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.
1 ≤ N, M ≤ 9
표에 적힌 숫자는 0보다 크거나 같고, 9보다 작거나 같다.
출력
첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.
풀이
N과 M의 범위가 9 이하로 매우 작다. 최대 81개의 칸에서 다시 전체 81개의 칸으로 건너뛰어보고, 그 간격에 따라 다음 칸들을 탐색해본다면 연산 횟수가 81*81*9(표가 9칸을 넘지 않음)를 넘지 않으리라는 것을 알 수 있다.
N*M크기의 표에 있는 모든 숫자를 대상으로 탐색을 시도한다. 각 탐색은 다시 표 안에 모든 칸으로 이어진다. 열과 행의 번호가 등차수열을 이루어야 한다고 했기 때문에 두 개의 칸을 정하면 둘 사이의 거리로 같은 거리로 탐색을 이어갈 수 있다. 이렇게 새 칸을 확인할 때마다 갖고 있던 숫자에 10을 곱하고 새로운 칸의 숫자를 더해준다. 만들어진 수가 기존 완전제곱수보다 크면 새 수가 완전제곱수가 맞는지 확인한다. 맞다면 가장 큰 완전제곱수를 바꿔준다.
여기서 첫 번째 칸과 두 번째 칸이 같은 경우, 공차가 0으로 무한하게 같은 칸을 반복해서 탐색하게 된다. 이런 경우는 첫 칸만 완전제곱수인지 확인하고 다음 탐색으로 넘어간다.
정답 코드
import sys
input = sys.stdin.readline
def is_power(k):
return True if k == (int(k**0.5))**2 else False
def solution():
N, M = map(int, input().split())
res = -1
table = [list(input().rstrip()) for _ in range(N)]
for i in range(N):
for j in range(M):
table[i][j] = int(table[i][j])
for i in range(N):
for j in range(M):
for x in range(-i, N - i):
for y in range(-j, M - j):
n = table[i][j]
if x == 0 and y == 0:
if is_power(n) and n > res: res = n
continue
dx = i + x
dy = j + y
while 0 <= dx < N and 0 <= dy < M:
n = n * 10 + table[dx][dy]
if is_power(n) and n > res: res = n
dx += x
dy += y
print(res)
solution()
