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

문제본문

문제 해석

어떠한 수 V(i)에 대해서 몫이 a고 나머지가 r이라면 아래의 수식이 성립한다.

  V(i) = a(i) * m + r(i)

 

그리고 V(i-1) 수식을 V(i) 뺀다면 아래와 같은 수식이 된다.

V(i) - V(i-1) = (a(i) - a(i-1)) * m + (r(i) - r(i-1))

 

자! 문제에서 원하는 답은 N개의 수에 대해서 M으로 나누었을 때 나머지가 같게되는 M을 모두 찾는 것이다. 나머지가 같다는 것은 위 수식에 대입해보면 답은 V(i) - V(i-1)의 숫자를 나머지가 0으로 만드는 M을 찾는 것이다.

 

N개의 수를 오름차순으로 정렬하기

  long[] nums = new long[n];

  for (int i = 0; i < nums.length; i++) {
     nums[i] = scanner.nextLong();
  }

  Arrays.sort(nums);

이 문제의 해결 과정은 N개의 수의 각 차이를 구해야 한다. 따라서 오름차순으로 정렬해야 음수가 나오지 않는다.
문제에 주어진 숫자의 범위는 1 ~ 10억이므로 int형의 범위를 넘어선다. 따라서 long형으로 배열을 선언해준다.

 

M 구하기 1 - 차이의 최대 공약수

 long x = nums[1] - nums[0];

 for (int  i = 2; i < nums.length; i++) {
     x = gcb(x, nums[i] - nums[i - 1]);
 }

숫자가 N개 있다면 N - 1개의 숫자들 사이의 차이(숫자)가 만들어 진다. 이 N - 1개의 숫자들의 나머지를 모두 0으로 만드는 M은 최대 공약수의 약수들이다. 여기서 최대 공약수를 찾는 방법인 유클리드 호제법 알고리즘이 나온다. 위 코드에서 gcb() 함수가 해당한다.

 

 //두 수 a,b의 최대 공약수 구하는 함수
    public static long gcb(long a, long b) {
        if (a % b == 0) {
            return b;
        }

        return gcb(b, a % b);
    }

 

M 구하기 2 - 최대 공약수의 약수들

단순히 최대 공약수의 약수를 찾기 위해서 1부터 접근하는 방법이 제일 간단하지만 숫자의 범위가 10억이므로 시간초과가 발생할 수 있다.
따라서 제곱근을 이용해서 약수를 찾는다.

  LinkedHashSet<Long> temp = new LinkedHashSet<>();
        // if x => 100,
        for (long i = 2; i * i <= x; i++) {
            if (x % i == 0) {   
                temp.add(i);   // x = 2,4,10 
                temp.add(x / i);  // x / i = 50,25,10
            } 
        }

제곱근을 이용한 약수 찾기 원리는 100 숫자로 예로 들수있다. 100의 제곱근은 10이기 때문에 10 x 10 = 100가 성립한다. 만약 오른쪽 피연산자가 제곱근보다 커지게 되면 4 * 25 = 100 수식을 성립하기 위해 왼쪽 피연산자는 제곱근보다 작아지게 된다. 따라서 제곱근까지의 수로 어떤 수의 약수를 모두 찾을 수 있다. 다만 중복이 발생하므로 주의 해야한다.

구한 약수에서 중복을 제거한 후, 오름차순으로 출력하면 답이다!

전체 코드

import java.util.*;

public class q2981 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        long[] nums = new long[n];

        for (int i = 0; i < nums.length; i++) {
            nums[i] = scanner.nextLong();
        }

        Arrays.sort(nums);
        long x = nums[1] - nums[0];

        for (int  i = 2; i < nums.length; i++) {
            x = gcb(x, nums[i] - nums[i - 1]);
        }

        LinkedHashSet<Long> temp = new LinkedHashSet<>();

        for (long i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                temp.add(i);
                temp.add(x / i);
            }
        }

        ArrayList<Long> list = new ArrayList<Long>(temp);
        Collections.sort(list);

        for(long num : list) {
            System.out.print(num + " ");
        }

        System.out.println(x);
    }

    //최대 공약수 구하는 함수
    public static long gcb(long a, long b) {
        if (a % b == 0) {
            return b;
        }

        return gcb(b, a % b);
    }
}

 

숫자 알고리즘 문제들은 구글링 없이 못풀 것 같다... 넘 어려워

 

참고

• 검문