[백준알고리즘] 2981번: 검문 -Python

[백준알고리즘] 2981번: 검문 -Python

https://www.acmicpc.net/problem/2981

2981번: 검문

 

이번 문제는 정답률이 21%인 난이도 높은 문제이다...

뭔가 감은 잡힌 것 같은데 식으로 만드는 데에 좀 오래 걸렸다..!

 

이런 문제일수록 예시를 더 줬으면 좋겠다 ㅠㅠ

 

 

문제를 풀기 위해서는 이전에 2609번 문제에서 유클리드 호제법으로 GCD(Greatest Common Divisor)을 구하는 것 외에 GCD를 구하는 다른 방법을 알면 좋다. 이건 링크를 구하지 못해서 설명을 하겠다.

 

임의의 두 수 X0와 X1 (X0 < X1)이 있다. 이때 X0와 X1는 gcd (gcd>=2)를 갖고 있다고 할 때 X0와 X1은 각각 다음과 같이 표현이 가능하다.

X0 = a * gcd

X1 = b * gcd

 

따라서 X1 - X0 = (b - a) * gcd 가 되고, 이것은 (X1 - X0)가 gcd의 배수임을 의미한다.

 

마찬가지로 임의의 두 수 X0와 X1 (X0 < X1)이 특정한 수로 나눴을 때 같은 나머지를 가지고 있을 때 다음과 같이 표현이 가능하다. (t는 임의의 정수)

X0 = a * t + r

X1 = b * t + r

X1 - X0 = (b - a) * t

 

위에서 (X1 - X0)가 gcd의 배수임을 의미했기 때문에 t도 gcd의 배수 혹은 약수일 것이다.

사전 설명은 이만하면 된 것 같다.

 

 

문제를 풀기 위해서는 입력받은 수들 중 가장 큰 수에서 가장 작은 수를 빼서 (b-a)*t를 구한 다음에 이 값의 모든 약수(+ 그 수 자체)에 대해서 나머지 값을 확인해고 같은 나머지 값들을 갖는 값만 출력하도록 하겠다.

 

import sys
import math

""" input """
N = int(sys.stdin.readline())
nums = []
for i in range(N):
    nums.append(int(sys.stdin.readline()))

nums.sort()

""" find divisors """
mog = nums[-1] - nums[0]
divisor = [mog]
for i in range(2, int(math.sqrt(mog)) + 1):
    if mog % i == 0:
        divisor.append(i)
        divisor.append(mog//i)

divisor = list(set(divisor))
divisor.sort()

""" get answer """
for d in divisor:
    for i in range(N):
        if i == N - 1:
            print(d, end = " ")
        elif nums[i] % d != nums[i + 1] % d:
            break

 

코드가 조금 길어 보이는데 가장 큰 수에서 가장 작은 수를 뺀 후 mog(multiple of gcd)에 저장을 하고, mog의 모든 인수 + 자기 자신을 리스트에 넣는다. (여기서 자기자신을 안 넣어서 많이 헤매었다.)

그런 다음 각 divisor 값마다 주어진 수들을 나눴을 때 나머지가 같은지 확인한다.

 

 

계속 수학3에서 쉬운 거 나와서 만만하게 보다가 큰코다쳤다..

 

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다