[BOJ/백준/C++] 2485번 가로수

2485번: 가로수

---

📌 접근 방법

• 유클리드 호제법을 사용하여 최대공약수를 구함

✔ 일반 함수

int GCD(int a, int b){
    int c = a%b;
    while(c!=0){
        a=b; 
        b=c;
        c=a%b;
    }
    return b;
}

 

✔ 재귀 함수

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

 

✅  Pass Code

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
using namespace std;
int GCD(int a, int b){
    int c=a%b;
    while(c!=0){
        a=b;
        b=c;
        c=a%b;
    }
    return b;
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    vector<int>v;
    cin>>N;
    int arr[N];
    for(int i=0; i<N; i++){
        int x;
        cin>>arr[i];
    }
    sort(arr, arr+N);
    for(int i=1; i<N; i++){
        v.push_back(arr[i]-arr[i-1]);
    }
    int tmp=v[0];
    for(int i=1; i<v.size(); i++){
        tmp=GCD(tmp, v[i]);
    }
    int cnt=0;
    for(int i=0; i<v.size(); i++){
        cnt+=v[i]/tmp-1;
    }
    cout<<cnt<<'\n';
    return 0;
}