[백준 2485 JAVA 자바] 가로수

이 문제의 핵심은 출력에 있습니다

 

"모든 가로수가 같은 간격이 되도록"

"새로 심어야 하는 가로수의"

"최소수"

 

각 핵심을 해석하면

 

"등차수열"

"등차수열 - 원래 심어져있는 나무"

"최대값"

 

이러면

아하!

이웃한 나무들 거리의 최대공약수를 찾으면 되구나!

생각이 됩니다

 

코드입니다

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	
    	int n = scan.nextInt();
    	
    	int[] arr = new int[n];
    	int[] gap = new int[n-1];
    	
    	arr[0] = scan.nextInt();
    	
    	for(int i=1; i<n; i++) {
    		arr[i] = scan.nextInt();
    		gap[i-1] = arr[i]-arr[i-1];
    	}
    	
    	int min = gcd(gap[0],gap[1]);
    	
    	for(int i=1;i<n-2;i++) {
    		if (gcd(gap[i],gap[i+1])<min) {
    			min = gcd(gap[i],gap[i+1]);
    		}
    	}
    	System.out.println(((arr[n-1]-arr[0])/min)-n+1);
    }
    
    static int gcd(int a, int b) {
    	while (b != 0) {
            int r = a%b;
            a=b;
            b=r;
        }
        return a;
    }
}

 

특히 여기서 최대 공약수를 구할 때

유클리드 호제법을 이용했습니다