[백준] [Brute Force] 제곱수 찾기

문제 소스 링크 : https://www.acmicpc.net/problem/1025

1025번: 제곱수 찾기

 

제곱수 찾기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

4297

1392

1105

31.973%

문제

N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.

연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.

연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.

입력

첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.

출력

첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.

제한

• 1 ≤ N, M ≤ 9
• 표에 적힌 숫자는 0보다 크거나 같고, 9보다 작거나 같다.

예제 입력 1

2 3
123
456

예제 출력 1

64

만들 수 있는 세자리 수는 123, 321, 456, 654이다. 이 중 완전 제곱수는 없기 때문에 정답은 64가 된다.

예제 입력 2

5 5
00000
00000
00200
00000
00000

예제 출력 2

0

0은 완전 제곱수이고, 입력으로 주어진 표에서 만들 수 있는 가장 큰 완전 제곱수이다.

예제 입력 3

6 7
3791178
1283252
4103617
8233494
8725572
2937261

예제 출력 3

320356

모든 i번 행의 i번 열에 적힌 수를 이어붙이면 320356을 만들 수 있고, 이 수는 5662 = 320356 이다.

예제 입력 4

5 9
135791357
357913579
579135791
791357913
913579135

예제 출력 4

9

홀수 숫자 두 개로 끝나는 완전 제곱수는 없다. 따라서, 만들 수 있는 가장 큰 완전 제곱수는 9이다.

예제 입력 5

9 9
553333733
775337775
777537775
777357333
755553557
355533335
373773573
337373777
775557777

예제 출력 5

-1

3, 5, 7만을 이용해 완전 제곱수를 만들 수 없다.

예제 입력 6

9 9
257240281
197510846
014345401
035562575
974935632
865865933
684684987
768934659
287493867

 

 

 

- 문제를 쉽게 이해하기가 어려움. 특히 아래의 문구

'행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다.' 라는 문제의 설명은 다음과 같이 해석될 수 있다.

=> 행의 index, 열의 index가 일정한 간격의 값을 가지고 있어야 한다. 이 때 공차값은 0과 음수값을 가질 수 있다

 

예시로, 주어진 수들의 나열에서 행/열의 등차 수열을 이루고 있는 값을 빨간색으로 표시해보면 다음과 같다.

- 이를 코드로 표현하는데 꽤나 많은 시간이 걸렸다. 일단, 행/열 m by n 에서 matrix[x][y] 는 모든 값이 시작값이 될 수 있다. 시작값에서 일정한 값을 가지고 등차 수열 이루려면, 시작 index [x][y]에서 -m <= dm < m, -n <= dn <n의 값이 더해진 값이 탐색되어야 하며, 모든 값을 검색하기 위해서는 계속 추가되는 값들을 더할 수 있어야 한다. 

 

- 선택된 값들이 제곱수 임을 확인하기 위해서는 math의 sqrt함수를 사용하여 확인한다. 다만, 이 값의 모든 형식이 float형이므로 원래 값에서 sqrt()의 값을 뺐을 때 0인 경우를 제곱수에 해당한다고 판단한다.

math.sqrt(4)
#2 
#type : float

 

- 코드 

import math

N, M = map(int, input().split())
numbers = []

for _ in range(N):
    temp = input()
    numbers.append([int(i) for i in temp])

answer = -1

for n in range(N): 
    for m in range(M):
        for dn in range(-N, N):
            for dm in range(-M, M):              
                if dn == 0 and dm == 0:
                    continue
                
                step = 0
                nnew = n
                mnew = m
                
                value = ''
                
                
                while (0 <= nnew < N) and (0 <= mnew < M):
                    value = value + str(numbers[nnew][mnew])
                    step = step + 1
                    cadi_value = int(''.join(value))
                    sqrt_value = math.sqrt(cadi_value)
                    value_decimal = sqrt_value - int(sqrt_value)
                    
                    if value_decimal == 0 and cadi_value > answer:
                        answer = cadi_value
                        
                    nnew = n + step * dn
                    mnew = m + step * dm
                    
                    
print(answer)

 

- 아래의 분의 코드를 참고하여 풀이 및 해설하였다.

https://nerogarret.tistory.com/41

[백준 알고리즘: python 3] #1025 - 제곱수 찾기