[백준] 1025번 제곱수 찾기

💡문제접근

• 행렬 상에서 모든 경우를 전부 탐색하여 완전 제곱수가 되는 숫자를 찾는 문제다. 이 때, 행 방향의 공차와 열 방향의 공차가 0일 때는 계속 같은 수만 이어붙이는 작업을 하기 때문에 이 상황이라면 Overflow Error가 발생한다. 따라서 공차가 0인 경우는 continue로 지나치는 과정을 거치도록 해야 한다.
• 위의 문제를 해결하고 다시 제출했는데 98%에서 틀렸다는 결과를 받았다. 질문게시판에 있는 내용을 확인했는데 N = 1, M = 1인 경우 코너케이스가 발생할 수 있다고 나와 있어서 해당 테스트케이스를 입력한 결과 제대로 나오지 않은 것을 확인할 수 있었다. 이 부분에 대한 에러를 해결한 후 다시 제출했더니 정상적으로 통과되었다.

💡코드(메모리 : 33376KB, 시간 : 80ms)

import math
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
table = [input().strip() for _ in range(N)]
answer = -1

def func(x):
    x = int(x)
    num = math.sqrt(x)
    if int(num) * int(num) == x:
        return True
    return False

if N == 1 and M == 1:
    result = int(''.join(map(str, table)))
    if func(result):
        print(result)
    else:
        print(answer)
else:
    for y in range(N):
        for x in range(M):
            for dy in range(-N + 1, N):
                for dx in range(-M + 1, M):
                    num = ""
                    current_y = y
                    current_x = x
                    if dx == 0 and dy == 0:
                        continue
                    while 0 <= current_x < M and 0 <= current_y < N:
                        num += table[current_y][current_x]
                        current_x += dx
                        current_y += dy
                        if func(num):
                            answer = max(answer, int(num))
    print(answer)

💡소요시간 : 47m