[백준 알고리즘: python 3] #1025 - 제곱수 찾기

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

 

1025번 문제는 제곱수 찾기입니다. 문제 해석부터 꽤 어려운 문제였습니다. 다행히 저만 그런 것은 아니었는지, 이 문제에 대한 질문 게시판에서 무슨 말인지 겨우 이해하게 됐네요. 걸어둔 링크를 참고해주시길 바랍니다.

 

Hint!

그러니까, 행과 열 번호가 모두 등차수열을 이루면서 만들어지는 제곱수 중 최대를 구하라는 것이네요. 다행히 입력받는 수의 개수가 최대 9 * 9 = 81개라서 크게 무리가 되는 양은 아니라서 전수조사를 하는 방향으로 했습니다. 전수 조사를 하는 요소는 (1) 행의 시작 위치, (2) 열의 시작 위치, (3) 행에 적용되는 공차, (4) 열에 적용되는 공차입니다. 한 가지 주의할 점은 공차가 음수와 0도 가능하다는 점입니다. 문제의 예제에서 답이 64인 이유는 (1, 2) (1, 0) 의 좌표의 숫자를 조합해서 만들었고, 여기서 열의 공차는 -2였다는 점을 확인하시면 이해가 편할거에요.

 

위 4가지 요소로 가능한 모든 경우를 조사해서 숫자를 조합하고, 조합이 될 때마다 그 숫자가 제곱수인지 확인한 후 최댓값을 갱신해주는 형태로 코드를 짜시면 됩니다. 코드가 길지 않아 주석을 좀 달아두었으니 (^^;;) 참고하시길 바래요!

 

다음의 코드로 성공하였습니다.

 

import sys
import math

M, N = map(int, sys.stdin.readline().split())

numbers = []
for _ in range(M):
    numbers.append(list(map(int, list(sys.stdin.readline().replace('\n', '')))))

result = -1

for m in range(M): # 어느 행에서 시작할 것인가?
    for n in range(N): # 어느 열에서 시작할 것인가?
        for weight_m in range(-M, M): # 행에서의 공차. -M부터 시작
            for weight_n in range(-N, N): # 열에서의 공차. -N부터 시작
                # 두 공차가 모두 0이면 무한 루프
                if weight_m == 0 and weight_n == 0: continue
                step = 0
                x = m
                y = n
                value = ''
                # 입력받은 수들의 범위 안에서 가능한 수열 추출
                while (0 <= x < M) and (0 <= y < N):
                    # 숫자 조합을 하고
                    value += str(numbers[x][y]))
                    step += 1

                    # 제곱수이고, 최댓값 갱신이 가능한지 확인
                    value_int = int(''.join(value))
                    value_sqrt = math.sqrt(value_int)
                    value_decimal = value_sqrt - int(value_sqrt)
                    if value_decimal == 0 and value_int > result: result = value_int

                    x = m + step * weight_m
                    y = n + step * weight_n

print(result)