[백준, BOJ] 1025 - 제곱수 찾기

1. Question

지민이는 천장을 보다가 직사각형 격자판을 생각했고, 각 칸에 숫자를 한 자리씩 적어 놓았다.

수업시간이 너무 지루해서 지민이는 행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열을 생각해 보았다. 그리고 나서 그 수열의 수를 모두 이어 붙였다. 이렇게 만든 수 중에 가장 큰 제곱수를 출력하는 프로그램을 작성하시오.

1.1 Input

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다.

1.2 Output

첫째 줄에 지민이가 만든 수 중에 가장 큰 제곱수를 출력한다. 만약 제곱수가 없다면 -1을 출력한다.

1.3 Example

입력	출력
2 3 123 456	64

2. Approach

문제 설명이 개 그지 같은 문제다.

주어지는 입력 테이블이 등차수열로 주어지고, 제곱수를 만들기 위한 원소들의 인덱스도 등차수열이다.

구현은 간단하나, 등차가 0 혹은 음수인 경우도 생각해야된다.

필자는 그지 같은 설명을 보고 빡쳐 조건을 제대로 보지 않은 나머지, 초기화를 -1이 아니고 0으로 해서 2번이나 틀렸다 ;;

3. Submission

4. Code

import math

Row, Col = map(int, input().split())
table = []
for _ in range(Row):
    table.append(input())

ans = -1
for row in range(Row):
    for col in range(Col):
        for rd in range(-Row, Row):
            for cd in range(-Col, Col):
                if rd == 0 and cd == 0:
                    continue
                
                string = []
                n = row
                m = col
                
                while (0 <= n < Row) and (0 <= m < Col):
                    string.append(table[n][m])
                    
                    val = math.sqrt(int("".join(string)))
                    if val == int(val):
                        ans = max(ans, int(val)**2)
                    
                    n += rd
                    m += cd
print(ans)