[백준_2485번] 가로수

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

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 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.

 

[코드]

import java.util.*;

public class BaekJoon_2485 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] position=new int[n];
		
		for(int i=0;i<n;i++)
			position[i]=sc.nextInt();
		
		// 각 가로수들의 간격을 구한다.
		int[] diff=new int[n-1];
		for(int i=0;i<n-1;i++)
			diff[i]=position[i+1]-position[i];
		
		// 간격들간의 최대 공약수를 찾는다.
		int gcd=gcd(diff[0],diff[1]);
		for(int i=2;i<n-2;i++) {
			gcd=gcd(gcd,diff[i]);
			
			if(gcd==1)
				break;
		}
		
		/*
		 * 예를 들어 가로수가 (1,3,7,13)에 심어져있다면 각 가로수간의 간격은
		 * (2,4,6)이 되고, 간격들의 최대 공약수는 2가 된다. 
		 * 그리고 (각 거리의 차를 최대 공약수로 나눈 몫) -1의 누적 합이 
		 * 설치해야하는 가로수의 개수가 된다.
		 */
		int count=0;
		for(int i=0;i<n-1;i++)
			count+=((diff[i]/gcd)-1);
		
		System.out.println(count);
	}
	
	// 유클리도 호제법으로 최대공약수를 구하는 함수
	public static int gcd(int a, int b) {
		while(b>0) {
			int temp=b;
			b=a%b;
			a=temp;
		}
		return a;
	}
}

 

[고찰]

 이번 문제는 가로수가 심어져 있는 위치의 차들의 최대공약수를 구하는 것이 중점인 문제이다. 최대공약수는 유클리드 호제법으로 간단하게 구할 수 있다. 구한 최대공약수의 값의 간격으로 가로수를 설치해야하기 때문에 각 가로수의 거리이 차를 최대공약수로 나눠준 값 - 1을 누적한 값이 정답이 된다. 이때 -1을 해준 이유는 최대공약수만큼의 차가 있는 가로수 사이에는 추가적으로 가로수를 설치할 필요가 없기 때문에 각 경우에서 해당 경우를 빼줘야하기 때문이다.