[2485] 가로수

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

2485번: 가로수

<문제>

나무를 심는 길이는 크면 클수록 좋다. 인접한 가로수 사이의 간격을 전부 __gcd()를 가하면

나무를 심는게 가능하면서, 길이가 최대인 값을 찾을 수 있다.

이 값을 찾은 뒤에는, ((가장 큰 값)-(가장 작은 값))/(나무를 심는 간격)-n+1이 답이된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, len, ans;
vector<int> a, v;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int i;
    a.resize(n);
    for (i = 0; i < n; i++) cin >> a[i];
    for (i = 0; i + 1 < n; i++) v.push_back(a[i + 1] - a[i]);
    len = __gcd(v[1], v[0]);
    for (i = 1; i < v.size(); i++) len = __gcd(len, v[i]);
    cout << (a[n - 1] - a[0]) / len - n + 1;
    return 0;
}