[백준] 가로수 2485 - JAVA

문제

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

2485번: 가로수

 

풀이

모든 가로수가 같은 간격이 되도록 심어야 한다.

이미 몇몇 가로수들은 심어져 있다. 그러면 가로수 간격이 모두 같으려면 어떻게 해야될까?이는 초등학교 수학문제에서 답을 찾을 수 있는데 바로 최대공약수이다.최대공약수를 이용하여 가로수의 간격을 구하고 이 간격에 따라서 가로수를 심어주면 된다.최대공약수를 구할때는 유클리드 호제법을 이용하였다.

유클리드 호제법은 x, y 의 최대공약수는 y, r 의 최대공약수와 같다는 원리를 이용한다.

즉, 계속해서 x 값에는 y 값을 대입하고 y 값에는 r 값을 대입하다보면 언젠가는 r 이 0 이 되는데 이때에 y 값에 있는 값이 최대공약수다.

 

코드

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

public class Main {
			
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		int n = Integer.parseInt(br.readLine());
		
		long arr [] = new long[n-1];
		
		long pre = Long.parseLong(br.readLine());
		for(int i=0;i<n-1;i++) {
			long cur = Long.parseLong(br.readLine());
			arr[i] = cur - pre;
			pre = cur;
		}
	
		long min = arr[0];
		for(int i=1;i<n-1;i++) {
			min = gcd(min, arr[1]);
		}
		
		int count = 0;
		for(int i=0;i<n-1;i++) {
			count += (arr[i] / min) - 1;
		}
		
		System.out.print(count);
		
	}
	
	static long gcd(long a, long b) {
		if(a%b == 0)
			return b;
		return gcd(b, a%b);
	}
   
}