📌 문제

[2485] 가로수

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

⬇️ 입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

⬆️ 출력

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

💡 코드

✅ 처음에는 주어진 위치들의 최대공약수를 구해야 되나 싶었는데, 같은 간격이 중요한 포인트이므로 간격 간의 최대공약수를 구해보자! 라는 마음으로 문제를 풀어봤는데 정답이였다!

이미 심겨진 나무들의 위치를 배열 arr에 담아 간격을 차례대로 구하기 위해 Arrays.sort()를 사용했는데, 지금 생각해보니 어차피 가까운 순서대로 값에 제공되기 때문에 정렬은 굳이 안했어도 됐을 듯? ㅎㅎ,,

어쨌든 배열의 요소들을 활용하여 간격 distance를 구한 뒤 간격 간의 최대공약수 gcd를 구할 수 있다. 유클리드 호제법은 기본적으로 두 수를 사용하여 최대공약수를 구하는데, n개의 나무에는 n-2개의 간격이 생기게 된다. 이를 해결하기 위해, for문을 통해 반복이 돌 때마다 생기는 distance와 앞서 구한 gcd를 사용하여 최대공약수를 구했다. 이 때, gcd의 초기값이 0인데 이 상태로 gcd()메서드를 수행하면 / by zero 예외가 발생하므로 gcd = 0인 경우에는 distance를 반환하도록 해야 한다.

간격에 따라 필요한 나무의 개수는 (마지막 나무 위치 - 처음 나무 위치) / 간격 + 1으로 구할 수 있고, 이미 n개의 나무가 심겨져있으므로 최종 정답은 필요한 나무의 개수 - n을 출력해주면 된다!

import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		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 gcd = 0;
		for(int i=0;i<n-1;i++) {
			int distance = arr[i+1] - arr[i];
			gcd = gcd(Math.max(distance, gcd), Math.min(distance, gcd));
		}
		bw.write((arr[n-1] - arr[0]) / gcd + 1 - n + "");
		
		br.close();
		bw.close();
	}
	
	static int gcd(int x, int y) {
		if(y == 0) return x;
		int z = x % y;

		if(z == 0) return y;
		return gcd(y, z);
	}
}