[백준/C++] 2485 가로수 (유클리드호제법, 최대공약수)

2485번: 가로수

이미 심어져있는 가로수의 개수 (N) 이 주어지고

가로수 N개의 각각의 위치가 주어진다.

주어진 위치의 간격을 모두 같은 간격으로 맞추고자할때

추가로 몇개의 가로수(count)가 필요한지 구하는 문제이다.

 

1. 주어진 가로수 위치의 간격을 구한다.

2. 모든 간격의 최대 공약수를 구한다. (유클리드 호제법 필요!)

3. 모든간격을 최대공약수로 나누어주되 시작점과 끝점이 주어져있으므로 -1하면 count가 된다.

 

유클리드 호제법과 최대공약수를 쉽게 이해할 수 있는 블로그를  참고하자 !

 

유클리드 호제법(Euclidean-algorithm)

+

최대공약수

최대공약수, 최대공약수 구하는 방법

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;
int Euclidean(int a, int b) { // 최대공약수 구하는 유클리드 호재법
	int r = a % b;
	if (r == 0) return b;
	else return Euclidean(b, r);
}
int main() {
    fastio;
	int N; // 처음주어지는 가로수의 수
	int gcd = 0; // 최대공약수
	int count = 0; // 추가할 가로수의 수
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tree[i]; // 가로수의 수만큼 거리(크기)입력
	}
	sort(tree, tree + N); // 정렬 함수
	for (int i = 0; i < N - 1; i++) { // 다음가로수의 위치와 현재가로수위치의 거리간격
		tree_distance[i] = tree[i + 1] - tree[i];
	}
	gcd = tree_distance[0]; // 가로수간의 최대공약수 구하는 반복문
	for (int i = 1; i < N - 1; i++) {
		gcd = Euclidean(gcd, tree_distance[i]);
	}
	for (int i = 0; i < N - 1; i++) { // 시작지점 끝지점을 제외해야해서 -1해준다.
		count += (tree_distance[i] / gcd) - 1;	
	}
	cout << count; // 필요한 가로수의 개수 출력
	return 0;
}