[JAVA] 백준 2485 가로수

2485번: 가로수 (acmicpc.net)

2485번: 가로수

 

풀이 과정 

 

- 같은 간격으로 가로수를 최소로 심기 위해서는 현재 주어진 가로수 간격의 최대 공약수 간격으로 가로수를 심어야 함

 1) 가로수들 사이의 간격을 구함

 2)거리를 일정하게 만들어야 하기 때문에 거리들의 최대 공약수를 구함

 3) (간격/최대공약수) -1 해준 뒤 모두 더함 

 

정답 

 

import java.util.Scanner;
import java.util.Arrays;

public class Main {
	//최대 공약수 
	public static int gcd(int a, int b)
	{
		if(b==0)
		{
			return a;
		}
		else
		{
			return gcd(b,a%b);
		}
	}
	
	
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        int num = sc.nextInt();
        int arr[] = new int[num];
        int gap[] = new int[num-1];
        int gcd  = 0; //간격의 최대공약수 
        int result = 0;
        
        for(int i=0; i<num; i++)
        {
            arr[i] = sc.nextInt();
        }
        
        Arrays.sort(arr);
        
        //간격 저장
        for(int i=0; i<arr.length-1; i++)
        {
        	gap[i] = arr[i+1]-arr[i];
        }
    	
        //간격의 최대 공약수 구하기 
        gcd = gap[0];
        for(int i=1; i<arr.length-1; i++)
        {
        	gcd = gcd(gcd,gap[i]);
        }
        
        //추가로 심어야 할 가로수들 개수 
        for(int i=0; i<arr.length-1; i++)
        {
        	result+=(gap[i]/gcd)-1;
        }
        
        System.out.println(result);
        
    }
}