[백준-파이썬] 1025: 제곱수 찾기

문제로 가기

행의 번호와 열의 번호를 각각 등차수열로 봐주면서, 그 칸의 숫자를 이어 붙인다. 그랬을 때 만들 수 있는 정수 중 가장 큰 완전 제곱수!를 구하는 문제였다.

나는 기억이 안나는 수학적 개념이 하나 있어서 쓴다..ㅎㅎ

등차 수열: 연속하는 두 항의 차이가 일정한 수열 위키백과

(이미지 출처- 위키백과) 이러한 식이 나온다. 여기에서 d(두 항의 차이)를 '공차'라고 부른다.

예) 1-3-5-7-9 (2씩 차이), 4-10-16-24-30 (6씩 차이), 1-1-1-1-1 (0씩 차이), 100-99-98-97-96(-1씩 차이)

설명 🗝

a1 즉 첫째 항과 d, 즉 공차를 상황에 따라서 다 봐줬다. N, M이 9보다 작으니 브루트포스하게 쭉~ 봐줘도 되겠다고 생각했다.

그래서 4중 for문이 나온다. 행의 첫째 항과 d, 열의 첫째 항과 d를 경우에 따라서 보니까!

위에 예시도 있듯이 공차는 양의 정수 뿐 아니라 음의 정수도 될 수 있고, 0도 될 수 있다! 그러니 공차의 범위를 열은 -N~ N, 행은 -M~M으로 잡아줬다.

둘 다 공차가 0이라면 무한 루프에 빠지고, '서로 다른 1개 이상의 칸을 선택'하라는 조건에 위배되니까 continue해줬다.

그리고 처음에는 공차가 음수인지 양수인지에 따라서 나눠서 계산했다.(정답 코드 1) 공차가 양수인지 음수인지에 따라서 range가 끝나는 기준이나 while 문에서도 i, j 의 범위가 달라진다고 생각했기 때문이었다.  그런데 문제 푼 후 생각해보니 이렇게 할 필요는 없을 듯... 그런 범위를 전혀 고려하지 않고 아래와 같이 하면 된다.(정답 코드 2)

0 <= i < N and 0 <= j < M

 

엄청 많이 틀렸다ㅠㅠ 틀린 이유는 등차 수열을 꼭 최대한 많이.. 끝까지 봐줄 필요는 없기 때문이었다!!!!!! 중간에 그만 두는 게 최선의 선택일 수도 있다.. 끝까지 봐주는 게 숫자가 크니까 좋을 것이라고 생각했는데, 그렇게 했다가 완전 제곱수가 안 될 수도 있으니까..

https://www.acmicpc.net/board/view/67386 이 게시물의 반례를 보고서야 알았다!!!!

정답 코드 👩‍💻

import sys
from math import sqrt

input = sys.stdin.readline

N, M = map(int, input().split())
board = list(input().rstrip() for _ in range(N))

ans = 0
flag = False


def check_perfect(tmp):
    global ans, flag
    # 완전 제곱 수인지
    tmp = tmp.replace(' ', '')
    if tmp:
        is_perfect_jegop = int(tmp) ** (0.5)
        if is_perfect_jegop == int(is_perfect_jegop):
            if int(tmp) == is_perfect_jegop ** 2:
                ans = max(ans, int(tmp))
                flag = True


for si in range(N):  # 열 등차 수열에서 시작하는 수
    for di in range(-N, N):  # 열 등차 수열에서 간격
        for sj in range(M):  # 행 등차 수열에서 시작하는 수
            for dj in range(-M, M):  # 행 등차 수열에서의 간격

                tmp = ''
                if di == 0 and dj == 0:  # 둘 다 등차가 0이면 안됨
                    continue

                # 등차 수열의 간격이 마이너스이면
                if di < 0:
                    final_i = -1
                else:
                    final_i = N

                if dj < 0:
                    final_j = -1
                else:
                    final_j = M

                # 어느 한쪽이 0일 때
                if di == 0:
                    for j in range(sj, final_j, dj):
                        tmp += board[si][j]
                        check_perfect(tmp)

                elif dj == 0:
                    for i in range(si, final_i, di):
                        tmp += board[i][sj]
                        check_perfect(tmp)

                else:
                    i = si
                    j = sj
                    # 등차 수열 간격이 둘 다 +
                    if di >= 0 and dj >= 0:
                        while (i < final_i) and j < final_j:
                            tmp += board[i][j]
                            i += di
                            j += dj
                            check_perfect(tmp)

                    elif di >= 0 and dj < 0:
                        while (i < final_i) and (j > final_j):
                            tmp += board[i][j]
                            i += di
                            j += dj
                            check_perfect(tmp)
                    elif di < 0 and dj >= 0:
                        while (i > final_i) and (j < final_j):
                            tmp += board[i][j]
                            i += di
                            j += dj
                            check_perfect(tmp)

                    elif di < 0 and dj < 0:
                        while (i > final_i) and (j > final_j):
                            tmp += board[i][j]
                            i += di
                            j += dj
                            check_perfect(tmp)

if flag:
    print(ans)
else:
    print(-1)

정답 코드 2👩‍💻

import sys
from math import sqrt

input = sys.stdin.readline

N, M = map(int, input().split())
board = list(input().rstrip() for _ in range(N))

ans = 0
flag = False


def check_perfect(tmp):
    global ans, flag
    # 완전 제곱 수인지
    tmp = tmp.replace(' ', '')
    if tmp:
        is_perfect_jegop = int(tmp) ** (0.5)
        if is_perfect_jegop == int(is_perfect_jegop):
            if int(tmp) == is_perfect_jegop ** 2:
                ans = max(ans, int(tmp))
                flag = True


for si in range(N):  # 열 등차 수열에서 시작하는 수
    for di in range(-N, N):  # 열 등차 수열에서 간격
        for sj in range(M):  # 행 등차 수열에서 시작하는 수
            for dj in range(-M, M):  # 행 등차 수열에서의 간격

                tmp = ''
                if di == 0 and dj == 0:  # 둘 다 공차가 0이면 안됨
                    continue

                i = si
                j = sj
                # 등차 수열 간격이 둘 다 +
                while 0 <= i < N and 0 <= j < M:
                    tmp += board[i][j]
                    i += di
                    j += dj
                    check_perfect(tmp)

if flag:
    print(ans)
else:
    print(-1)