BOJ 2485 - 가로수

재밌는 문제라 포스팅하고자 한다.

연속된 숫자 1,5,10 이라고 한다면 심어야할 나무는 1보다 작은 위치 또는 10을 넘어가는 위치에 심을 순 없다.  따라서 1-5 간격과 5-10 간격이 다르기 때문에 각 구간에 나무를 심어야되는데, 그 간격을 정해보는 것에 포커싱을 맞춰보자. 1-5 간격은 4, 5-10 간격은 5다. 따라서 2도 3도 4,5 모두 간격으로 둘 수 없다. 따라서 1간격으로 나무를 심을 수 밖에 없다.

반면 1,5,11 이라고 가정해보자. 1-5 간격은 4, 5-11 간격은 6이 된다. 따라서 2간격만큼 나무를 심어줄 수 있다.

모든 구간에 대해 같은 간격으로 나눠져야하기 때문에 최대공약수를 이용해 구한다.

모든 간격에 대해 최대공약수를 구하면 그것을 나눈 값 - 1로 답을 구할 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
int gcd(int a, int b) { int t; while (b) { t = a%b; a = b; b = t; } return a; }
int main() {
	int N, *A,g,i,ans=0;
	scanf("%d", &N);
	A = new int[N];
	for(i=0;i<N;i++) scanf("%d", &A[i]);
	sort(A, A + N);
	g = gcd(A[1] - A[0], A[2] - A[1]);
	for (i = 2; i < N - 1; i++)
		g = gcd(g, A[i + 1] - A[i]);
	for (i = 0; i < N - 1; i++)
		ans += (A[i + 1] - A[i]) / g - 1;
	printf("%d", ans);
	return 0;
}