[Baekjoon] 1025. 제곱수 찾기

🔗 Problem Link

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

---

❔Thinking

• 주어진 표에서, 일정한 간격으로 이동하며 숫자를 선택해 완전 제곱수를 만든다.
• 만들 수 있는 완전 제곱수 중 가장 큰 수를 반환한다. 완전 제곱수를 만들 수 없는 경우 -1을 반환한다.
• 완전 제곱수는 어떤 정수를 제곱한 수이다.

---

💻Solution

import sys, math
input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(input().rstrip()) for _ in range(N)]

def check(num: int):
    return math.isqrt(num) ** 2 == num

answer = set()
for row_k in range(N+1):
    for col_k in range(M+1):
        if row_k == 0 and col_k == 0:
            continue
        for i in range(N):
            for j in range(M):
                for dr, dc in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
                    tmp_num = []
                    start_i, start_j = i, j
                    while 0 <= start_i < N and 0 <= start_j < M:
                        tmp_num.append(board[start_i][start_j])
                        num = int(''.join(tmp_num))
                        if check(num):
                            answer.add(num)
                        start_i += dr * row_k
                        start_j += dc * col_k

print(max(answer, default=-1))

---

🗝️keypoint

1. 일정한 간격이란 등차수열을 말하며, 9x9 표이기 때문에 모든 경우의 확인이 가능하다.
2. 행과 열의 이동 간격이 모두 0인 경우, 이동이 불가능하기 때문에 넘어가야 한다.