백준 알고리즘 1025번 파이썬 제곱수 찾기

오늘 백준 1025번을 풀었습니다.

문제를 먼저 보자면

문제

배열에서 행과 열을 각각 등차수열에 맞게끔 선택하여 그 수가 제곱수가 되면 되는 것입니다.

보자마자 전부 봐야될 것 같아서 브루트포스 알고리즘 같았는데..

어떻게 풀어나갈지 공차를 설정하는 부분에서 헤매다가 다른 분의 소스를 공차 부분만 살짝 보고 만들어 보았습니다.

 

입력 출력 제한

제한에서 n,m이 1에서 9까지인 것을 보고 완전탐색을 해도 시간 초과는 안나겠구나 해서 방향성은 확실히 잡았습니다.

 

코드

import sys
from math import sqrt
input=sys.stdin.readline

n,m=map(int,input().split())
board=[list(map(str,input().strip())) for _ in range(n)]
ans=-1
#행
for i in range(n):
	#열
    for j in range(m):
    	#행에 대한 공차
        for tolY in range(-n,n):
        	#열에 대한 공차
            for tolX in range(-m,m):
            	#둘다 0이면 무한 루프를 돌기 때문에 continue로 넘겨줍니다.
                if tolY==0 and tolX==0:
                    continue
                #값을 이어붙여야하기 때문에 int가 아닌 str로 받아서 붙이기 위해 선언합니다.
                num=''
                y=i
                x=j
                #index에러가 안나는 범위에서 루프
                while 0<=x<m and 0<=y<n:
                	# num에 하나씩 이어 붙여줍니다.
                    num+=board[y][x]
                    # num의 제곱근의 제곱 값이 num과 같다면 제곱 수 임을 확인하는 부분
                    if int(sqrt(int(num)))**2 == int(num):
                    	# 기존 값과 비교하여 큰 값을 ans에 저장
                        ans=max(int(num),ans)
                    #공차만큼 각 행과 열을 변화해줍니다.
                    y+=tolY
                    x+=tolX
print(ans)

이렇게 짯습니다.

처음에는 공차를 step으로 넣어서 루프 문을 돌려보려고 시도를 해봤는데

잘 안되서 고민 끝에 힌트를 얻어 이렇게 작성을 하게 되었습니다.

또 한가지 잘 안됐던 부분이 type을 통해서 int이면 완전 제곱 수임을 확인해보려 했는데

sqrt를 돌리면 정수도 float 값으로 나오는데 int로 감싸주면 무조건 int가 되고 해서 확인이 불가능하더라고요.

그래서 제곱근의 제곱 값이 원래 값과 같다면 이어나가는 조건문으로 변경하였습니다.

 

알고리즘을 보고 풀어나가는 과정이 확실히 문제를 풀면 풀수록 속도도 빨라지고 접근도 빨라지는 것 같아요.

골드 하위 문제까지는 웬만하면 풀어나갈 수 있는 수준에 가까워진 것 같습니다.

더 열심히해서 플레문제도 씹어먹고 싶네요.

풀이가 도움이 되셨다면 공감 부탁드립니다.