[알고리즘 문제] Streetree

import java.util.*;
public class Main{
    public static void main(String[] args){
     
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int first,last;
        int GCD;
        int[] ary = new int[n];
        int[] gap = new int[100000];

        for(int i=0;i<n;i++){
          ary[i]=sc.nextInt();
          
          if(i>0){
            gap[i-1]=ary[i]-ary[i-1];
          }
        }
  
      for (int j = 1; j<n; j++) {
         gap[j] = gcd(gap[j],gap[j-1]);
      }
        
        GCD = gap[n-1];
        first = ary[0];
        last = ary[n-1];
        
      System.out.println(((last-first)/GCD-n+1));
    }
    
    static int gcd(int a,int b){
      if( a % b==0){
        return b;
      }else{
        return gcd(b,a%b);
      }
    }
}

문제는 간단하다. 1,5,7,11,13위치에 나무가 심어져 있을 때, 각 나무의 간격을 일정하게 하려면 어느 위치에 나무를 최소한으로 심어야 하는지 묻는 문제이다. 답은 3,9위치에 나무를 심으면 1,3,5,7,9,11 나무사이의 간격이 2로 일정한 간격을 유지할 수 있게 된다.

 

아이디어는  입력받은 나무들 간의 간격을 모두 구하고, 그 값들의 최대공약수를 구하는 것이다. 만약 2,10,14,18,30 위치에 나무들이 심어져 있으면 간격은 8,4,4,12가 될 것이다. 여기서 공약수는 2,4이다. 이 말은 나무의 간격은 2와 4의 배수위치에 나무들이 심어져 있다는 말이다. 하지만 나무의 간격이 2,4 모두 일정한 간격이지만 문제에서는 나무를 최소한으로 심어야 한다. 4로 심으면 간격은 일정하고 나무는 덜 심을 수 있다. 

 

입력받은 나무 마지막 위치-첫번째 위치를 하면 나무가 심어져 있는 총 거리를 알 수 있다. 거기에 아까 구한 4를 나누고+1을 하면  4의 일정한 간격만큼 총 몇개의 나무를 심을 수 있는지 알 수 있다.  여기에 처음 입력받은 n개의 나무를 빼주면 추가적으로 심어야하는 나무의 개수를 알 수 있다.