[C++] 백준 2485번: 가로수

문제 링크

2485번: 가로수

문제 요약

기준점으로부터 가로수들이 떨어져 있는 거리가 주어진다. 그 사이사이에 가로수를 추가적으로 심어서 각 가로수 사이의 간격을 동일하게 만들고자 한다. 이를 위해 심어야할 가로수 수의 최솟값을 구해야 한다.

접근 방법

최대공약수를 이용하면 해결할 수 있습니다.

먼저 원래 심어져 있는 가로수들 간의 간격의 최대공약수를 구합니다. 그리고 이 최대공약수에 해당하는 간격마다 가로수를 추가적으로 심어야 합니다. 그렇게 심으면 최소 갯수의 가로수를 심어 간격을 동일하게 만들 수가 있습니다.

매 간격마다 ((가로수 사이 간격) / (최대공약수) - 1)의 가로수를 필요로 하게 됩니다. 이를 모두 합해주면 답을 구할 수 있습니다.

최대공약수는 유클리드 호제법을 통해서 구할 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b)
{
	if (a < b)
		swap(a, b);
	return (a % b == 0 ? b : gcd(b, a % b));
}

int main(void)
{
	int n, res = 0;
	cin >> n;

	vector<int> v(n), diff;
	for (auto& i : v)
		cin >> i;

	for (int i = 0; i < n - 1; i++)
		diff.push_back(v[i + 1] - v[i]);

	int g = gcd(diff[0], diff[1]);
	for (int i = 2; i < diff.size(); i++)
		g = gcd(g, diff[i]);
;
	for (auto& i : diff)
		res += i / g - 1;

	cout << res << endl;
	return 0;
}