[Baekjoon] 1025. 제곱수 찾기

코딩테스트/Python

[Baekjoon] 1025. 제곱수 찾기

swwho 2025. 1. 30. 20:05

728x90

🔗 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))