(Python/파이썬) - 백준(BOJ) 1025번 : 제곱수 찾기

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

1025번: 제곱수 찾기

---

• 문제 : 

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

 

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

 

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

 

 

 

---

• 풀이 :

수학, 구현 문제였습니다.

 

N과 M이 최대 9기 때문에 O(n^5) 으로 충붆히 해결 가능하다고 판단하여 브루트포스로 모든 경우를 탐색했습니다.

 

알고리즘입니다.

 

1. 모든 좌표에 대해 -N부터 N까지의 범위로  등차를 지정하여 반복문 실행

 

2. 시작 좌표부터 등차를 더해주며 board 밖으로 벗어나지 않는 동안 방문한 좌표의 숫자들을 이어 붙여줍니다.

 

3. 매 좌표를 탐색할 때마다 해당 수가 완전 제곱수인지 판별하여 완전 제곱수라면 정답을 갱신해줍니다.

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

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

def sqr(S):
    S = int(S)
    return int(S ** 0.5) ** 2 == S


for i in range(N): #시작 x좌표
    for j in range(M): # 시작 y좌표
        for row_d in range(-N,N): # 행의 등차
            for col_d in range(-M,M): # 열의 등차
                S = ""
                x,y = i,j
                if row_d == 0 and col_d == 0:
                    continue
                while 0 <= x < N and 0 <= y < M:
                    S += board[x][y]
                    if sqr(S):
                        answer = max(answer,int(S))
                    x += row_d
                    y += col_d
print(answer)