백준 알고리즘 - 2485번: 가로수 [Java]

문제: https://www.acmicpc.net/problem/2485

2485번: 가로수

1. 코드

import java.util.*;
public 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();
		Arrays.sort(arr);
		
		int GCD = 0;
		for(int i = 1; i < N; i++)
			GCD = gcd(arr[i] - arr[i - 1], GCD);
		System.out.println((arr[N - 1] - arr[0]) / GCD + 1 - N);
	}
	
	private static int gcd(int a, int b) {
		if(b == 0) return a;
		return gcd(b, a % b);
	}
}

2. 설명

int GCD = 0;
for(int i = 1; i < N; i++)
    GCD = gcd(arr[i] - arr[i - 1], GCD);
System.out.println((arr[N - 1] - arr[0]) / GCD + 1 - N);

가로수의 간격들의 최소공배수를 기준으로 등차수열의 개수를 구하면 가로수의 총 개수이기에 이점을 이용하여 해결 가능합니다.