[BOJ] 2981번 검문

[BOJ] 2981번 검문 문제

굉장히 까다로운 수학 문제다. 애초에 검문을 하는데 뭔 이상한 문제를 왜 푸는지 모르겠지만 그래야 문제가 되니까...

---

이 문제의 조건은 $ 2 \leq N \leq \: 100 $의 정수가 들어오고, 각 정수는 1보다 크거나 같고 1,000,000,000(10억) 보다 작다. 이 숫자들을 $ M $으로 나눌 때 나오는 나머지의 값이 같아야 한다. 그때 1보다 큰 $ M $을 전부 구해야 하는 것이 목표다.

일단 문제를 처음 보면 굉장히 정신이 아찔해지는데, 먼저 이 문제를 이해해보자.

문제에서는 $ M $이 존재하는 경우만 테스트 케이스로 주어지기 때문에 확실히 나뉘어지는 수가 있다고 가정할 수 있다.

그렇다면 예를 들어 입력으로 주어지는 수열 $ A[0], A[1], ..., A[N-1] $이 있다고 하자. 위의 조건으로 인해 이 $ A[0], A[1], ..., A[N-1] \: $는 아래와 같이 적어볼 수 있다. 여기서 // 는 몫만 구하는 파이썬의 기호다.

$ A[0] = (A[0] \; // \; M) \times M + r $
$ A[1] = (A[1] \; // \; M) \times M + r $
$ ... $
$ A[N-1] = (A[N-1] \; // \; M) \times M + r $

 

여기서 $ r $은 $ M $으로 나눴을 때 나오는 나머지로, 문제의 조건으로 인해 수열 $ A $ 모두 같은 $ r \: $이 나와야 한다. 이 부분이 문제의 큰 핵심이라고 본다. 그렇다면 이 $ r \: $에 대해서 식을 다시 바꿔보자.

$ r = A[0] - (A[0] \; // \; M) \times M $
$ r = A[1] - (A[1] \; // \; M) \times M $
$ ... $
$ r = A[N-1] - (A[N-1] \; // \; M) \times M $

 

즉, 위의 있는 모든 수식의 우변은 전부 같다. 이를 두 개씩 짝지어서 식을 다시 전개하면 아래와 같이 된다.

$ A[1] - A[0] = (A[1] \; // \; M - A[0] \; // \; M) \times M $
$ A[2] - A[1] = (A[2] \; // \; M - A[1] \; // \; M) \times M $
$ ... $
$ A[N-1] - A[N-2] = (A[N-1] \; // \; M - A[N-2] \; // \; M) \times M $

 

$ r \:$이 수식에서 사라짐으로써 풀기가 더 쉬워졌다! 이 수식을 통해, 주어진 수의 차이들의 모든 최대공약수가 $ M \: $이 되고, 유클리드 호제법을 이용해 구한 이 $ M \: $을 이용하여 문제를 계속 풀어가야 한다.

---

근데 의문점이 든다. 저렇게 인접하는 수들의 차이만으로 모든 수의 최대공약수를 얻을 수 있는가? $ A[N-1] - A[0] \: $은 안 써도 답이 되는가? $ A[3] - A[1] \: $은? 실제로 본인도 이 부분에서 꽤 많은 시간을 소비했다.

이 의문점에 대한 나의 잠정적인 결론은 다음과 같다. 먼저 나머지 연산은 뺄셈에 대해 닫혀있다. 이게 무슨 말이냐 하면 뺄셈이 된 나머지 연산은 분배 법칙이 성립한다는 뜻이다. 나머지 연산의 분배 법칙은 아래와 같으며, 중간에 $ X \: $를 더해주는 이유는 음수가 되는 것을 막기 위함이다.

$ (a - b) \: mod \: X = ((a \: mod \: X) - (b \: mod \: X) + X) \: mod \: X $

 

이게 왜 갑자기 튀어나왔냐면, 결국 우리는 수열 $ A \: $의 나머지를 같게 해주는 $ M \: $을 구하는 것이 목적이며, 유클리드 호제법을 이용하여 최대 $ M \: $을 구하는 것이 목표이다. 그리고 나머지 $ r \:$을 없애고 유클리드 호제법을 사용하기 위해서 뺄셈을 사용하였다.

이를 잘 생각해보면, 결국 위에 나오는 연립식은 인접한 수열 요소끼리 뺄셈으로 엮여있지만 모든 수열 요소를 한 번씩 걸쳐 최대공약수를 구하는 것으로 이해될 수 있다. 실제로도 N개의 최대공약수를 구하기 위해선 N-1번의 유클리드 호제법을 이용해 최대공약수를 구할 수 있고, 그때 모든 수가 최소 1번씩 알고리즘에 넣어지는 것을 알 수 있다.

그렇기 때문에 나머지 연산이 뺄셈에도 닫혀있고, 모든 수가 최소 1번씩 유클리드 호제법에 넣어지기 때문에 N-1개의 인접하는 수의 차이만으로도 최대공약수를 구할 수 있고, 그 방법이 이 문제에서는 가장 빠르게 최대공약수를 구할 수 있는 방법이라는 잠정적인 결론을 내렸다.

어디까지나 잠정적인 결론이기 때문에, 틀릴 수도 있다. 이 부분에 대한 의견은 언제나 환영한다.

[추가] 다행히 이 말이 맞다는 한 피드백을 얻었다.

---

다시 본론으로 가서, 유클리드 호제법을 이용하여 구한 $ M \: $은 최대공약수이며, 이보다 더 큰 $ M \: $은 존재하지 않는다. 그렇다는 것은, 모든 수열의 수들은 $ M \: $의 약수로 나눠도 같은 나머지를 내어준다! 그렇기 때문에 $ M \: $을 구한 이후엔 $ M \: $의 모든 약수를 구하고, 거기서 문제에서 언급한 대로 1만 쏙 빼주면 그게 바로 문제의 정답이라는 뜻이다.

import sys

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

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    num_list = list()
    for _ in range(N):
        num_list.append(int(sys.stdin.readline().rstrip()))
    num_list.sort()
    now_gcd = num_list[1] - num_list[0]
    for i in range(1, N-1):
        now_gcd = gcd(now_gcd, num_list[i+1]-num_list[i])

    yaksu = {now_gcd}
    for i in range(2, int(now_gcd**0.5)+1):
        if now_gcd%i == 0:
            yaksu.add(i)
            yaksu.add(now_gcd//i)

    print(*sorted(list(yaksu)))

 

입력받은 수들을 정렬함으로써 뺄셈으로 인해 음수가 되는 것을 방지한다. $ 2 \leq N \leq 100 \: $이기 때문에 정렬하는 데에는 오래 걸리지 않는다. 다른 방법으로는 정렬하지 않고 뺄셈 이후 절댓값을 씌우는 것인데, 아무래도 이해하는 데엔 정렬이 가장 편하니 입력받은 수를 정렬하는 코드를 정식 코드로 내세웠다.

그 이후에는 약수를 구한다. $ Y \: $라는 수를 소인수 분해하기 위해선 $ \sqrt{Y} $ 만큼의 수 안에서 나눠지는 것들과 그 짝을 찾으면 된다. 100을 예시로 잡고 생각하면 된다. 약수 집합을 set으로 설정한 이유는 제곱수의 약수를 구할 때 나오는 약수 중복 방지를 위함이다.

이 문제에서는 1보다 큰 $ M \: $을 원하므로 이 코드에선 약수 집합에 미리 현재의 최대공약수를 넣고, 소인수 분해를 할 때 2부터 $ \sqrt{now \_ gcd} \: $까지만 돌리며, 이때 나온 약수들을 전부 약수 집합에 넣은 이후 정렬하여 출력한다.