[백준 1025번] 제곱수 찾기(파이썬)

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

1025번: 제곱수 찾기

이건 하나 하나 모든 경우를 다 봐야하는

완전탐색의 유형입니다.

시간이 많이 걸릴 것 같은 유형의 문제.

이 문제를 푸는데

파이썬이라서 다행이라는 생각.

파이썬은 상대적으로 자료형을 다루는 것이

C에 비하면 확실히 쉬운 편.

 

이 문제를 풀 때는

가로,세로 축을 다 보면서

공차도 하나하나씩 다 바꿔가면서

모든 경우를 다 따져야합니다.

길찾기 문제에 익숙한 저는

'이런 식이면 시간초과떠서 터질 것 같은데'

라고 생각했지만

이 문제는 그렇게 풀라고 아예 나온 문제.

#백준 1025번 제곱수 찾기
from  math import sqrt


N,M=map(int,input().split())

A=[list(map(int,input()))for _ in range(N)]

answer=-1

for i in range(N):
    for j in range(M):
        for d1 in range(-N,N):
            for d2 in range(-M,M):
                num=''
                x,y=i,j
                while 0<=x<N and 0<=y<M:
                    num+=str(A[x][y])
                    if d1==0 and d2==0:
                        break
                    if int(sqrt(int(num)))**2==int(num):
                        answer=max(int(num),answer)

                    x+=d1
                    y+=d2

print(answer)

 

 

이 문제를 푸는 데 있어서

파이썬 자료형 변환에 대해서 연습해볼 수 있기 때문에

자료형 변환에 대해서 연습하기 좋은 문제입니다.