백준 1025번_제곱수 찾기 (Python)

문제

N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.

연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.

연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.

첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.

첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.

 

코드

N, M = map(int, input().split())
matrix = [[] for i in range(N)]
for i in range(N):
    matrix[i] = input()
ans = -1
for i in range(N):
    for j in range(M):
        for k in range(-N, N):
            for m in range(-M, M):
                if k == 0 and m == 0:
                    continue
                temp = ''
                x, y = i, j
                while 0<=x<N and 0<=y<M:
                    temp = temp+matrix[x][y]
                    if int(temp) == int(int(temp)**0.5)**2:
                        ans = max(ans, int(temp))
                    x += k
                    y += m
print(ans)

 

해설

간단한 브루트포스 문제다. 숫자의 배열에서 가능한 모든 x, y의 좌표의 등차수열의 초항과 등차를 구해준 뒤 가능한 범위만큼 수열의 길이를 하나하나 늘려가며 제곱수인지 확인해주면 된다.

다만, 주의해야 할 것이 우선 x와 y의 등차가 모두 0일 경우 프로그램이 제자리에서 맴돌게 되므로 예외 처리를 해줘야 한다. 또한, 수는 방향에 따라 달라지기 때문에 등차는 당연히 음수도 고려해주어야 한다.

그리고 가장 헷갈렸던 부분인데, 자꾸 틀렸습니다가 나와서 모범 코드를 찾아봤는데 for k in range와 for m in range에서 범위를 -N부터 N-1, -M부터 M-1까지로 잡아뒀던 것이다. 어차피 등차가 -N이나 -M이면 배열 길이가 1을 초과하는 순간 이미 불가능해지기 때문에 범위를 -N+1부터 N-1 등으로까지 하면 안되나였다. 하지만 이렇게 하면 입력이

1 1
9

같이 제공된 경우에 for k in range(0, 0)으로 반복문이 아예 작동하지를 않는데, 그러면 배열 길이가 1인 경우도 확인하지 못한다. 그렇게 되면 코드는 가능한 제곱수가 없다고 표시하는데, 실제로 '9'라는 제곱수를 만들 수 있으므로 틀린 결과가 된다. 그래서 쓸모없어 보여도 저런 경우를 위해서 어쩔 수 없이 반복문 범위를 저렇게 집어넣은 것이었다.