2981 : 검문 - Python

접근

---

처음에는 ((A % M) + (B % M)) % M = (A+B) % M 을 사용하는 문제라고 생각했다. A + B == C일 때, ((A % M) + ((C - A) % M)) % M = C % M를 활용하면 될 것 같았는데, 수가 최대 1,000,000,000까지이므로 인덱스를 어디로 잡는지가 문제였다.

 

제한 시간이 초과되었고, 알고리즘을 확인해보니 유클리드 호제법이 있었다. 이전에도 몇 번 접했지만 자주 쓰지 않을 거라고 판단해서 그 때 그 때마다 찾아서 확인했었다. 자주 접하게 되어서 아예 에라토스테네스의 체처럼 기억을 해둘 필요를 느꼈다.

 

유클리드 호제법

두 양의 정수 a, b(a > b)에 대하여 a = bq + r (0 ≤ r < b)이라면, a, b의 최대공약수는 b, r의 최대 공약수와 같다. r이 0이라면 a, b의 최대 공약수는 b가 된다.
gcd(a, b) = gcd(b, r)

 

반복문 방식

def euclidean(a, b):
    while b != 0:
        a, b = b, a % b
    return a

재귀 방식

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

알고리즘을 확인하고 유클리드 호제법으로 최대 공약수를 구하고 이를 어떻게 활용할까 고민했는데 도저히 못풀겠어서 풀이를 참고했다.

풀이

---

[백준 2981] - [수학 최대공약수] - 검문 (JAVA)

핵심은 “…수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다.” 였다.

 

수를 a[0], a[1], a[2] … 라고 하고 모든 수에 대해서 M으로 나누었을 때 나머지가 모두 같다면 아래와 같은 상태가 된다.

 

a[0] % M = a[0] - (a[0] / M) * M

a[1] % M = a[1] - (a[1] / M) * M

a[2] % M = a[2] - (a[2] / M) * M

…

---

위 식에 대해 (a[0] % M) = (a[1] % M) = (a[2] % M) 이 성립하고 a[0] - (a[0] / M) * M = a[1] - (a[1] / M) * M 역시 성립한다. 또한 a[0] - (a[0] / M) * M = a[1] - (a[1] / M) * M는 a[0] - a[1] = M * ((a[0] / M) - (a[1] / M))로 바꿀 수 있다.

 

이를 통해 어떤 수에서 다른 수를 빼면 M의 배수가 된다는 것을 알 수 있다. 그러므로 A[0] - A[1] ~ A[i - 1] - A[i]까지의 공약수를 모두 찾아주면 된다.

자꾸 이상한 실수를 한다...

def find_div(gcd):
    result = []
    for div in range(2, (gcd >> 1) + 1): # 이 부분이 문제
        if gcd % div == 0:
            result.append(div)
    result.append(gcd)
    return result

gcd >> 1을 gcd // 2가 아닌 gcd ** 0.5로 착각했다. pypy로 제출하면 pypy가 너무 빠르게 때문에 통과한다. 정답이 나오니까 로직에 이상은 없다고 생각하고 어느 부분이 시간이 많이 걸릴까 고민했다.

뭔가 이상함 깨닫기까지 한 시간이 걸렸고 너무 허무했다. 최대 5억의 숫자를 모두 나눠보는 바보같은 일을 하고 있었다. 수의 절반까지 나누니까 당연히 약수들이 모두 포함되었고, 여기서 따로 gcd // div를 추가하지 않아도 되었다.

gcd ** 0.5로 하게 되면 두 수를 모두 넣어줘야 한다. 그리고 이 과정에서 어떤 수가 제곱수라면 중복되기 때문에 set을 활용하는 것이 좋다.

def find_div(gcd):
    ans = set()
    for div in range(2, gcd ** 0.5 + 1):
        if gcd % div == 0:
            ans.add(div)
            ans.add(gcd // div)
        ans.add(gcd)
    return ans

전체 코드

 

import sys

# print = sys.stdout.write
input = sys.stdin.readline
# 반드시 아래 두 라인 주석 처리 후 제출
f = open("input.txt", "rt")
input = f.readline
# 반드시 위 두 라인 주석 처리 후 제출

N = int(input().rstrip())

arr = sorted([int(input().rstrip()) for _ in range(N)], reverse=True)

def find_div(gcd):
    result = set([gcd])
    for div in range(2, int(gcd**0.5) + 1):
        if gcd % div == 0:
            result.add(div)
            result.add(gcd // div)
    return result

def euclidean(a, b):
    if a < b:  # 항상 a > b를 보장
        a, b = b, a

    while b:
        a, b = b, a % b
    return a

def main():
    gcd = arr[0] - arr[1]
    for i in range(1, N - 1):
        # 제공되는 a,b에 대해 a > b를 보장해줄 수 없음.
        gcd = euclidean(gcd, arr[i] - arr[i + 1])

    print(" ".join(map(str, sorted(find_div(gcd)))))

if __name__ == "__main__":
    main()