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

문제

나의 답안

n,m=map(int,input().split())
s=[]
res=-1

for _ in range(n):
    s.append(list(input()))

for col in range(n):#행 
    for row in range(m):#열
        for i in range(-n,n):#행 방향 공차
            for j in range(-m,m):#열 방향 공차
                num=''#완성된 숫자 저장
                x,y=row,col#열, 행

                while x>=0 and x<m and y>=0 and y<n:#입력된 범위 안에서
                    if i==0 and j==0:#공차가 0이면 같은 칸을 선택한 것(문제 조건 위배)이고
                                    #무한루프 되므로 정지
                        break
                    #가능한 숫자 조합
                    num+=str(s[y][x])
                    if int(int(num)**0.5)**2==int(num):#어떤 성수를 제곱한 수인지(완전제곱수)
                        res=max(int(num),res)#최대 제곱수 구하기
                        
                    y+=i#행 증가
                    x+=j#열 증가
                    
print(res)
        

접근 방법

• 1. 행의 공차를 구해야 한다. (행의 시작 위치를 지정해야 함)
• 2. 열의 공차를 구해야 한다. (열의 시작 위치를 지정해야 함)
• 3. 완전제곱수를 구하고, 해당 제곱수가 최대인지 판별해야 한다.
     위의 3단계를 거치면 된다.
• 행의 공차를 구하기 위해 행을 기준으로 공차를 구해주고(ex-(1,1),(1,2),(1,3)), 열의 공차도 구해준다.
• x와 y 각각을 열과 행으로 초기화 해준다.
• 행과 열 범위 안에서 while 반복문을 돌리는데 이때 공차가 0이면 같은 칸을 선택한 것이므로 서로 다른 1개 이상의 칸을 선택해야 하는 문제 조건에 위배된다. 따라서 해당 공차가 0이면 반복문을 중단한다.
• 공차가 0이 아니라면 가능한 숫자를 계산해준다.
• 해당 숫자가 제곱 수인지 판별하기 위해 제곱근을 계산해준 후 해당 제곱근을 제곱하여 원래 수와 같은지 확인한다.
  • 만약 같다면 완전 제곱수이므로 기존 제곱수와 비교해 최댓값인지 판별한다.
• 위와 같은 과정을 끝내면 다음 행과 열로 넘어가기 위해 y+=i x+=j 을 해준다.
• 모든 반복문을 돌았다면 결과값인 res를 출력해준다.