[백준 2485번] 가로수 (C++)

문제링크 : http://acmicpc.net/problem/2485

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
int arr[100001];
vector<int>v;
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;

    for(int i=0; i<N; i++) cin >> arr[i];

    for(int i=0; i<N-1; i++)
    {
        v.push_back(arr[i+1] - arr[i]);
    }

    int tmp = v[0];
    for(int i=1; i<v.size(); i++) tmp = gcd(tmp, v[i]);
    
    int result = 0;
    for(int i=0; i<v.size(); i++) result += (v[i]/tmp-1);

    cout << result;

    return 0;
}

 

최대공약수를 활용한 문제이다.

각 거리의 간격을 살펴보면 다음과 같다.

1 3 7 13
간격 : 2, 4, 6 (필요 0개, 1개, 2개)

 

각 간격의 최대 공약수를 구하면 2다.

필요 갯수를 살펴보면 해당 간격/최대공약수 - 1을 하면 각 간격의 필요 개수인 것을 알 수 있다.