[Python] 백준 1025 - 제곱수 찾기 문제 풀이

Boo Sung Jun·2022년 3월 9일
1

알고리즘, SQL

목록 보기
30/70
post-thumbnail

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문에서 숫자를 조합하여 제곱수가 맞는지 확인하여 답을 구한다.

0개의 댓글