테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 제곱수 찾기 ======

===== 풀이 =====
  * 발상에 걸린 시간: 매우 짧음 / 구현에 걸린 시간: 매우 짧음
  * N의 범위가 작으므로, 그냥 조건을 만족하는 정수들을 일일히 다 찾아서 제곱수인지 확인하는 방법으로 하면 풀린다.
  * 시작 셀의 좌표와, 행의 공차, 열의 공차, 길이 가 정해지면, 해당되는 정수를 찾을 수 있다. 이걸 모든 경우에 다 해보려면 5중루프가 되어서 코드가 좀 지저분하긴 하지만.. 그래도 그게 구현하기 가장 간편한것 같다
  * 시간 복잡도는 저대로 5중루프를 생각하면 O(N^2*M^2*min(N,M)).

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1025. 제곱수 찾기".

- Problem link: https://www.acmicpc.net/problem/1025
- Solution link: http://www.teferi.net/ps/problems/boj/1025

Tags: [Brute Force]
"""

import math


def main():
    N, M = [int(x) for x in input().split()]
    grid = [[int(x) for x in input()] for _ in range(N)]
    
    answer = -1
    for r_start in range(N):
        for c_start in range(M):
            for r_step in range(-N, N):
                for c_step in range(-M, M):
                    if r_step == c_step == 0:
                        continue
                    num = 0
                    r, c = r_start, c_start
                    while 0 <= r < N and 0 <= c < M:
                        num = num * 10 + grid[r][c]
                        if math.isqrt(num)**2 == num:
                            answer = max(num, answer)
                        r, c = r + r_step, c + c_step
    print(answer)


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}