Overview
BOJ 1025번 제곱수 찾기 Python 문제 풀이
분류: Brute Force (완전탐색)
문제 페이지
https://www.acmicpc.net/problem/1025
풀이 코드
from sys import stdin
from math import sqrt
def main():
n, m = map(int, stdin.readline().split())
arr = [stdin.readline().rstrip() for _ in range(n)]
res = -1
for i in range(n): # i: 시작 행 위치
for j in range(m): # j: 시작 열 위치
for a in range(-n, n): # a: 행 방향 등차
for b in range(-m, m): # b: 열 방향 등차
num = ''
y, x = i, j
# 행과 열 시작 위치부터 등차를 더해가며 숫자 생성
while 0 <= y < n and 0 <= x < m:
num += arr[y][x]
if a == 0 and b == 0:
break
if int(sqrt(int(num))) ** 2 == int(num):
res = max(int(num), res)
y += a
x += b
print(res)
if __name__ == "__main__":
main()
행렬에서 모든 경우의 수를 만들며 답을 탐색한다.
이를 위하여 4중 for문과 while문을 이용한다. 가장 바깥쪽 for문 2개는 행의 시작 위치와 열의 시작 위치를 정한다. 그 다음 for문 2개는 행 방향 등차와 열 방향 등차를 정한다. 등차는 음수도 가능하며, 등차의 절대값은 행의 길이 또는 열의 길이보다 클 수 없다. 마지막으로 가장 내부 while문에서 숫자를 조합하여 제곱수가 맞는지 확인하여 답을 구한다.
