[BOJ/solved.ac] [Python] 1025 제곱수 찾기

1025번: 제곱수 찾기 (acmicpc.net)

1025번: 제곱수 찾기

 

문제

N행 M열의 표에서, 행 번호가 선택한 순서대로 등차수열을 이루고 있고,

열 번호도 선택한 순서대로 등차수열을 이루고 있게 선택한 칸에

적힌 수를 순서대로 이어붙여 만든 정수 중에 가장 큰 완전 제곱수(어떤 정수를 제곱해서 만든 수) 구하기

(완전 제곱수를 만들 수 없으면 -1 출력)

# 등차수열 : 어떤 수와 그 수에 차례로 일정한 수(공차)를 더하여 얻어지는 수열

 

제한 조건

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

 

예시

# 입력 예시
2 3
123
456

# 출력 예시
64

해설
(1,2)에 위치한 6 -> (1,0)에 위치한 4
행은 공차가 0인 등차수열, 열은 공차가 -2인 등차수열


# 입력 예시
6 7
3791178
1283252
4103617
8233494
8725572
2937261

# 출력 예시
320356

해설
(0,0) -> (1,1) -> (2,2) -> ... -> (5,5)
행과 열은 공차가 1인 등차수열

---

풀이

# 32952 KB / 76ms

# isqrt : 음이 아닌 정수의 양의 제곱근보다 크지 않은 가장 큰 정수
# (제곱수일 경우 양의 제곱근, 제곱수가 아닐 경우 int(양의 제곱근))
from math import isqrt

# 행의 수와 열의 수, 표 내용 입력 받기
N, M = map(int, input().split())
table = [input() for _ in range(N)]

# max_num 정의
max_num = -1

# 표에서 선택해 만든 숫자가 완전제곱수인지 판별 후, max_num 갱신
def is_square_num(num):
    global max_num
    num = int(num)
    if max_num >= num:
        return
    root = isqrt(num)
    if root ** 2 == num:
        max_num = num

# 표에서 숫자 선택해 새 숫자 만들기
def dfs(row, col, number ,level=0, row_dif=0, col_dif=0):
    if level == 0:
        for k in range(N):
            for l in range(M):
                if k != row or l != col:
                    new_num = number+table[k][l]
                    is_square_num(new_num)
                    dfs(k, l, new_num, level+1, k-row, l-col)
    else:
        new_row, new_col = row+row_dif, col+col_dif
        if 0 <= new_row < N and 0 <= new_col < M:
            new_num = number + table[new_row][new_col]
            is_square_num(new_num)
            dfs(new_row, new_col, new_num, level, row_dif, col_dif)

# 선택된 숫자의 첫 번째 숫자 결정
for i in range(N):
    for j in range(M):
        is_square_num(table[i][j])
        dfs(i,j,table[i][j])
        
print(max_num)

---

해설

1. 새로 만들 수의 첫 번째 값을 2중 for문을 이용해 결정

2. 이 수가 가장 큰 제곱수(max_num) 값보다 크면, 제곱수인지 판별하고 제곱수라면 max_num 갱신
   (is_square_num 실행)

3. dfs 함수 실행

4. level이 0이면 (첫 번째 수만 존재할 경우) 두 번째 수를 2중 for문을 이용해 결정

5. is_square_num 실행

6. dfs(k, l, new_num, level+1, k-row, l-col) 실행
   (각 인자는 순서대로 행 번호, 열 번호, 새로 만든 수, 첫 번째만 수만 존재하는지 여부, 행의 공차, 열의 공차)

7. level이 0이 아닐 경우, 기존 행의 공차와 열의 공차를 이용해 다음 행 번호, 열 번호 계산

8. 다음 행 번호와 열 번호가 표의 행과 열 내에 있으면 새로 만든 수를 계산한 후, is_square_num, dfs 실행

9. 최종 max_num 출력