[백준] 2485번 - GCD(최대공약수) 응용

>>문제 바로가기<<

가로수들이 띄엄띄엄 심어져 있을 때, 일정한 간격으로 가로수를 추가로 심으려면 최소 몇개를 심어야 하는지를 묻는 문제이다.

---

n번째 가로수와 1번째 가로수의 차에서
gcd (최대 공약수)를 나누게 되면
우리가 목표로 하는 간격수가 나오게 된다.

추가적으로 심어야 하는 가로수 수는 위 식에서 +1을 하고 현재있는 가로수 수를 빼면 된다.
(간격+1 = 목표로 하는 나무 개수)

최소 공약수가 아닌 최대 공약수를 구하는 이유는 심어야 하는 가로수의 갯수를 최소로 맞추기 위함이다.

위 정보를 토대로 설계한 코드는 다음과 같다.

import java.util.*;

class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
        	arr[i] = sc.nextInt();
        }
        
        int[] diff = new int[N-1];	// 간격 집합
        for(int i=0; i<diff.length; i++){
        	diff[i] = arr[i+1] - arr[i];
        }
        
        int gcdValue = diff[0];
        for(int i=0; i<diff.length; i++){
        	gcdValue = gcd(gcdValue, diff[i]);
            // gcd를 계속해서 갱신하여 최적의 gcd 탐색
        }
        
        int totalTree = (arr[N-1] - arr[0]) / gcdValue + 1;
        int result = totalTree - N;	// 구하려는 전체 가로수 - 현재 가로수
        
        System.out.println(result);
    }
    
    public static int gcd(int a, int b){
    	while(b != 0){
        	int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
}

맞았습니다!!