[백준] 2981 검문

문제보기

간만에 수학으로 푸는 문제였다.

핵심은 주어진 수열을 오름차순(내림차순도 괜찮다)으로 나열했을 때 인접한 두 수열간의 차이들 간의 최소공배수를 구해줘야 한다는 것이었다. 구해준 최소공배수의 약수들을 쭉 나열하면 정답이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Main {

  // 최소공배수 구하는 메서드 
  static int gcb(int a, int b) {
    while(b != 0){
      int r = a%b;
      a = b;
      b = r;
    }
    return a;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];
    for(int i = 0 ; i < n ; i++) {
      arr[i] = Integer.parseInt(br.readLine());
    }
    Arrays.sort(arr);// 주어진 배열은 정리한다.
    int[] a = new int[n-1]; // 인접한 원소간 차이를 저장할 새로운 배열 
    for(int i = 0 ; i < n-1 ; i++) {
      a[i] = arr[i+1] - arr[i];
    }
    // 최소공배수를 저장할 변수 
    int g = 0;
    if( n-1 > 1 ) { // 주어진 n > 2 일 경우 
      // 원소간 차이들의 최소공배수를 구한다 
      g = gcb(a[0], a[1]);
      for(int i = 2 ; i < n-1 ; i++){
        g = gcb(g, a[i]);
      }

    }else { // 주어진 n = 1 인 경우는 차이값이 하나밖에 없다
      g = a[0];
    }
    Stack<Integer> st = new Stack<Integer>();
    st.add(g);
		// 스택에 해당 최소공배수의 약수를 저장한다.
    for(int i = g-1 ; i >= 2 ; i--) {
      if(g%i == 0) st.add(i);
    }
    // 출력
    StringBuilder sb = new StringBuilder();
    while(!st.isEmpty()) {
      sb.append(st.pop() + " ");
    }
    System.out.println(sb);
  }
}