백준 2485 - 가로수

가로수 사이의 거리를 일정하게 만들 수 있도록 가로수를 심어야 하는 문제입니다.

가로수 사이 거리를 구한 다음 최대공약수를 구하고 거리에서 최대공약수를 나눈 값에 -1을 해주고 모두 더하면 됩니다.

최대공약수는 유클리드 호제법을 통해 쉽게 구해낼 수 있지만, 제 코드에서는 단순하게 거리 중 가장 작은 수를 골라내고 1부터 가장 작은 수까지 돌면서 다른 수들과 나머지를 구해 공약수를 구했습니다.

#include <iostream>

int main()
{
	int n;
	int* nums;
	int* dists;

	std::cin >> n;
	nums = new int[n];
	dists = new int[n - 1];

	for (int i = 0; i < n; i++)
		std::cin >> nums[i];

	for (int i = 0; i < n - 1; i++)
		dists[i] = nums[i + 1] - nums[i];

	int j = 0;
	for (int i = 0; i < n - 1; i++)
	{
		int key = dists[i];
		for (j = i - 1; j >= 0; j--)
		{
			if (key > dists[j])
				nums[j + 1] = nums[j];
			else
				break;
		}
		nums[j + 1] = key;
	}

	int min = 1;

	for (int i = 1; i <= dists[0]; i++)
	{
		bool isPass = true;
		for (int j = 0; j < n - 1; j++)
		{
			if (dists[j] % i != 0)
			{
				isPass = false;
				break;
			}
		}
		if (isPass)
			min = i;
	}

	int result = 0;
	for (int i = 0; i < n - 1; i++)
	{
		result += dists[i] / min - 1;
	}

	std::cout << result;

	delete[] nums;
	delete[] dists;

	return 0;
}