Python - [백준]1025-제곱수 찾기

문제

각 행, 열이 등차수열을 이루는것들로 골라 그 수를 이어붙인 수를 찾고 그 중 가장 큰 제곱수를 찾는 문제이다.

접근 방법

우선 문제와 예제를 보면, 0을 포함한 등차수열로 이루어진 행과 열을 고른다. 그 중 음수도 포함된다.
입력 크기가 그렇게 크지 않기때문에, 모든 경우에 대해 탐색을 진행하고 답을 구하는 방식으로 진행하였다.

• 모든 행과 열 i, j에 대해 탐색을 시작한다
• 등차수열의 간격을 -n, -m부터 n, m까지 설정하여 탐색을 진행하고, 제곱수 여부를 검사하여 기존 값보다 더 큰 제곱수라면 초기화 해준다.
• 만약 차이가 i, j가 모두 0이 된다면 무한루프에 빠지게 되므로, 그 경우는 건너뛰게 예외처리를 해준다.

풀이

시작 위치를 정해줄 행과 열에 대한 for문 2개를 배치한다.
이후 등차간격을 정해줄 하위 for문 두개를 생성하고, 그것에 대해 모든 경우를 탐색해줄 while문을 하나 더 추가해준다.
만약 내가 이어붙인 값이 제곱수이면서 더 큰경우, result값을 초기화해준다.

코드

from math import sqrt
n, m = map(int, input().split())

arr = [list(map(int, input())) for _ in range(n)]
result = -1
def is_sqrt(x):
    if int(sqrt(int(x))) ** 2 == int(x):
        return True
    else:
        return False

for i in range(n):
    for j in range(m):
        for diff_x in range(-n, n):
            for diff_y in range(-m, m):
                tmp = ''
                x, y = i, j
                if diff_x == 0 and diff_y == 0:
                    continue
                while 0 <= x < n and 0 <= y < m:
                    tmp += str(arr[x][y])
                    if is_sqrt(tmp):
                        result = max(result, int(tmp))
                    x += diff_x
                    y += diff_y

print(result)