코딩테스트/백준

[백준] 2485 : 가로수 - JAVA

ankisile 2023. 12. 3. 02:05

문제

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

 

2485번: 가로수

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

www.acmicpc.net

 

코드

import java.util.*;
import java.io.*;

class Main {	
	
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int arr [] = new int [n];
		
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		int interval = 0;
		for(int i=1;i<n;i++) {
			interval = gcd(arr[i]-arr[i-1], interval);
		}

		int answer = 0;
		for(int i=1;i<n;i++) {
			answer += (arr[i] - arr[i-1])/interval - 1;
		}
		System.out.print(answer);
	}

	static int gcd(int a, int b) {
		if(b == 0) return a;
		return gcd(b, a%b);
	}
}