[알고리즘] 백준 2485번: 가로수 (C++)

https://www.acmicpc.net/problem/2485

2485번: 가로수

똑같은 간격으로 가로수가 들어가야 했다.

>> 간격들을 구하여 간격들의 최대공약수를 구하여 {((각 간격) / (최대 공약수)) - 1(간격 사이기 때문에 -1)}을 구해주면 풀리는 문제였다.

 

>> 최대공약수는 유클리드 호제법으로 구해주었다.

 

[AC 코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;

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

int main(){
    cin >> n;
    vector<int> v;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    
    vector<int> diff;
    for(int i = 1; i < n; i++){
        diff.push_back(v[i] - v[i - 1]);
    }
    
    sort(diff.begin(), diff.end());
    
    int gcdValue = gcd(diff[0], diff[1]);
    for(int i = 1; i < diff.size(); i++){
        gcdValue = gcd(diff[i], gcdValue);
    }
    
    int result = 0;
    for(int i = 0; i < diff.size(); i++){
        result += (diff[i] / gcdValue) - 1;
    }
    
    cout << result;
    return 0;
}