[BOJ 2981] 검문(Java, 유클리드 호제법, Set)

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

2981번: 검문

 

 

이 문제 풀이의 핵심은 유클리드 호제법이다.

 

 

 

유클리드 호제법은 어떤 수 a와 b가 있을 때(a > b), a와 b의 최대공약수는 b와 a % b와 동일하다.

 

 

 

증명은, 다음 유튜브를 참고하길,

 

 

 

https://www.youtube.com/watch?v=J5Yl2kHPAY4

 

 

 

1. 인접한 수들을 정렬한다. 

 * 정렬의 이유는, gcd에 들어가는 매개변수가 음수가 되지 않기 위해서이다. 음수가 되지 않도록 조건을 단다면, 굳이 정렬하지 않아도 된다.

 

 

 

2. 인접한 수의 뺄셈의 최대 공약수를 구하면서, 최대 공약수를 갱신한다.

 * 전체의 최대 공약수를 구하는 것은 부분의 최대 공약수를 이용해서 구하는 것과 동일하다.

 

 

 

3. 최대 공약수의 약수들을 출력한다.

 

 

 

---

* 인접한 수의 뺄셈의 최대 공약수를 구하는 것이 왜 나머지가 모두 동일한 M을 구하는 것일까?

 

 

 

n1, n2, n3을 나머지를 동일하게 만드는 수 최대 공약수 A가 있다고 가정하자.(n1 < n2 < n3)

 

 

 

n1 % A = n2 % A

n2 % A = n3 % A

 

 

 

첫 번째 식에서 n1 % A를 빼주고, 두번째 식에서 n2 % A를 빼주면,

 

 

 

n1 % A - n2 % A = n3 %A - n2 % A

(n1 - n2) % A = (n3 - n2) % A

 

 

 

인접한 수의 뺄셈의 최대 공약수를 구하는 것이 정답을 구할 수 있게 된다.

 

---

 

해설코드(C++).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static Scanner sc;
    static int N, val;
    static int[] arr;
    static HashSet<Integer> hSet;
    
    public static void main (String[] args) throws java.lang.Exception
    {
        sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N + 1];
        hSet = new HashSet<Integer>();
        
        for(int i = 1; i <= N; i++){
            val = sc.nextInt();
            arr[i] = val;
        }
        
        int gcd;
        if(arr[2] > arr[1])
            gcd = arr[2] - arr[1];
        else
            gcd = arr[1] - arr[2];   
        
        for(int i = 2; i < N; i++){
            if(arr[i + 1] > arr[i])
                gcd = GCD(gcd, arr[i + 1] - arr[i]);
            else
                gcd = GCD(gcd, arr[i] - arr[i + 1]);
        }    
        
        for(int i = 1; i <= gcd; i++){
            if(gcd % i == 0){
                hSet.add(gcd / i);
                hSet.add(i);
            }
        }
        
        hSet.remove(1);
        TreeSet myTreeSet = new TreeSet();
        myTreeSet.addAll(hSet);
        Iterator<Integer> itr = myTreeSet.iterator();
        
        while(itr.hasNext()){
            System.out.print(itr.next() + " ");
        }
        System.out.println();
    }
    
    public static int GCD(int a, int b){
        if(a % b == 0)
            return b;
        else
            return GCD(b, a % b);
    }
}