[Python/파이썬] SW Expert Academy 20731번 서로소 그리드

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AY6ci8cKecUDFAXt&categoryId=AY6ci8cKecUDFAXt&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

코드

def gcd(a, b):  # a와 b의 최소공배수 구하기
    if b == 0:
        return a
    return gcd(b, a % b)


for tc in range(1, int(input())+1):
    n = int(input())
    board = [input() for _ in range(n)]

    possible = [True]*1000

    for i in range(n):
        for j in range(i+1, n):
            for k in range(1000):
                if possible[k]:
                    res = gcd(i+1+k, j+1+k)
                    if res == 1 and board[i][j] == '1':
                        continue
                    elif res != 1 and board[i][j] == '?':
                        continue
                    else:
                        possible[k] = False
    ans = "NO"
    for i in range(1000):
        if possible[i]:
            ans = "YES"
            break
    print(f"#{tc} {ans}")

 

 

행과 열에 같은 숫자를 더한 두 수가 서로소인지 아닌지 우선 판별해야 한다. 이를 알아보기 위하여 최대공약수를 구하는 유클리드 호제법을 이용한다.

def gcd(a, b):  # a와 b의 최대 공약수 구하기
    if b == 0:
        return a
    return gcd(b, a % b)

 

이 함수를 수행했을 때 리턴값이 1이면 서로소이고, 그 이상의 수이면 서로소가 아니다.

 

이것을 이용하여 (1, 1)칸부터 (N, N)칸까지 탐색하며 격자판의 정보와 일치하는 k를 찾아낸다. 이때 모든 격자판을 확인할 필요는 없다. 왜냐하면

1. (1, 1), (2, 2)와 같이 왼쪽 맨 위에서 오른쪽 맨 아래로 내려오는 대각선에 있는 칸들은 행과 열이 같은 수이기 때문에 여기에 어떤 수를 더해봤자 두 수의 최대공약수는 i+k(=j+k)이다.
2. 이 대각선을 기준으로 대칭되는 칸, 예를 들자면 (2, 5)와 (5, 2)는 행과 열에 같은 수 K를 더하여 GCD를 구한 결과값이 같기 때문이다. 즉, 대각선을 기준으로 대칭되는 칸은 격자판의 정보값이 똑같으므로 둘 중 하나만 확인해도 된다.

그러므로 대각선 위의 칸들만 확인해서 시간을 최대한 줄여서 완전탐색을 해준다.

 

처음에는 k의 범위로 가능한 숫자를 [0,50)까지로 했는데 테스트 케이스를 80%정도만 맞아서 범위를 더 늘려봤더니 맞았다.