2485번: 가로수 [C++]

문제

 

 

풀이

먼저, 주어진 나무의 위치를 받아 오름차순으로 정렬한다. 그리고 각 나무 사이의 간격을 구하고 그 간격들의 최대공약수를 구한다. 이 최대공약수만큼의 간격을 가지고 나무를 심으면 가장 적게 심을 수있다.

(개수를 셀 때 -1을 해주는 것은 양 쪽에 나무가 심겨져 있기 때문이다.)

#include <iostream>
#include <algorithm>

using namespace std;

int trees[100000];
int betweenTree[100000];

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

int main() {
	int n;
	int count = 0;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> trees[i];

	sort(trees, trees + n);

	for (int i = 1; i < n; i++)
		betweenTree[i - 1] = trees[i] - trees[i - 1];

	int interval = betweenTree[0];

	for (int i = 1; i < n - 1; i++)
		interval = gcd(interval, betweenTree[i]);

	for (int i = 0; i < n - 1; i++)
		count += betweenTree[i] / interval - 1;

	cout << count;

	return 0;
}