2981. 검문 (Python)

 

2981번: 검문

 

풀이

 입력 받은 각 수 들의 차이에 대하여 최대 공약수를 구한다. 

  위의 예제를 보자. 입력으로 받은 [5, 17, 23, 14, 83]에 대하여 자신의 앞에 있는 숫자와의 차이를 구하면 [12, 6, 9, 69]가 나온다. 이제 이 숫자들에 대하여 차례대로 최대 공약수를 구한다. 12와 6의 최대 공약수를 구하면 6이 나온다. 다시 이 6과 9의 최대 공약수를 구하면 3이 나온다. 다시 3과 69에 대하여 최대 공약수를 구하면 3이 나온다. 최종적으로 입력으로 받은 숫자들에 대하여 같은 나머지를 얻을 수 있는 숫자 M은 1을 제외한 3의 약수가 된다.

 

 사실 뭔가 수학적으로 접근해서 문제를 해결한 건 아니고 모르겠어서 그냥 이렇게 저렇게 아무거나 해보다가 맞췄다 ㅎ. 그래서 문제를 풀고나서 구글링을 통해 이에 대한 이유를 찾아봤다. 자세한건 링크를 참고하자....

 

 위에서 구한 최대 공약수의 약수를 구하여 출력할 때 단순히 반복문만 사용하면 시간이 오래 걸리니 제곱근을 사용하여 출력하도록 하자.

 

코드

import math


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


if __name__ == '__main__':
    N = int(input())
    nums = [] # 입력으로 받는 숫자
    subNums = [] # 입력으로 받은 숫자의 차이를 담는 리스트

    for _ in range(N):
        nums.append(int(input()))

    for i in range(1, N): # nums[i] - nums[i-1]의 값을 subNums에 담는다.
        subNums.append(abs(nums[i] - nums[i-1])) 

    gcdNum = subNums[0] # 그 후 subNums에 있는 숫자들의 최대 공약수를 구해준다.
    for i in range(1, N-1):
        gcdNum = gcd(gcdNum, subNums[i])

    res = set()
    for i in range(2, int(math.sqrt(gcdNum)) + 1): # 약수를 구하는 시간을 단축하기 위해 제곱근 사용
        if gcdNum % i == 0:
            res.add(i)
            res.add(gcdNum // i)

    res.add(gcdNum)
    print(' '.join(map(str, sorted(list(res)))))