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

컴퓨터/백준 알고리즘

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

이상한 나그네 2023. 9. 21. 00:35

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

2485번: 가로수

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가

www.acmicpc.net

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);

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