[BOJ] 2981번 검문 / 사용언어 : 파이썬(python)

※ 문제링크

2981번: 검문

※ 관련 개념

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

해당문제는 나머지정리와 유클리드 호제법을 사용해서 풀어야하는 문제였다. 처음에는 단순히 브루스포트방식으로도 풀 수 있지 않을까 해서 해당 방식으로 풀어봤는데 역시나 시간초과가 나왔다. 그 후에는 나머지 정리와 DFS방식으로 변환하여 풀었더니 통과가 가능한 것으로 확인하였다. 문제풀이를 위해서는 나머지 정리와 유클리드 호제법에 대한 이해가 필요하며, 이 문제에서 사용한 방법은 아래와 같다.

1. m으로 나누었을 때 나머지 n이 모두 같다고 가정하고, 나머지 정리를 사용하면 xn = myn + n이 됨.

2. x0 = my0 + n과 xn = myn + n을 도출가능하며, 이 식을 연립하여 정리하면, (xn - x0) = m(yn - y0)의 식이 성립함.

3. 즉, 두 수의 차이를 구하고 해당 수의 약수를 구하면 문제에서 원하는 답을 구할 수 있음.

4. 두 수 차이의 조합을 구하기 위해 DFS와 백트래킹을 통해 두 수의 차이 조합을 구하고, 중복제거 진행.

5. 중복을 제거한 후에는 하나 하나씩 나눠보면서 해당 수의 약수를 순서대로 구하고 출력.

6. 약수를 구할때는 시간 절약을 위해 제곱근까지만 반복문을 걸고 나머지는 계산으로 구한 후 중복제거 및 정렬.

위의 개념을 이용하여 풀어본 코드는 아래와 같다.

 

import sys
input = sys.stdin.readline
N = int(input())
number_list = [int(input()) for  _ in range(N)]
check_list = [False] * N
arr = []
r_list = []
def dfs(start): # dfs를 활용하여 두개의 숫자조합 및 가능한 차이값 추출
    if len(arr) == 2:
        r_list.append(abs(arr[0]-arr[1]))
        return

    for i in range(start, N):
        if check_list[i]:
            continue

        arr.append(number_list[i])
        check_list[i] = True

        dfs(i)

        arr.pop()
        check_list[i] = False
dfs(0)
r_list = list(set(r_list)) # 차이값 중 중복되는 값들 제거

result = r_list[0]
def euclid(num1, num2): # 큰 수, 작은 수 순으로 입력
    num3 = num1 % num2
    if num3 == 0:
        return num2
    else:
        result = euclid(num2, num3)
        return result

for i in range(1, len(r_list)): # 유클리드 호제법을 활용하여 최대공약수 추출
    if result > r_list[i]:
        result = euclid(result, r_list[i])
    else:
        result = euclid(r_list[i], result)


answer = []
for check in range(2, int(result**(1/2) + 1)):
    if result % check == 0:
        answer.append(check)
        answer.append(result // check)
answer.append(result)
answer = list(set(answer))
answer.sort()
print(*answer)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.