백준 2485 (가로수) / C++

문제 링크 : https://www.acmicpc.net/problem/2485

2485번: 가로수

> 풀이

 

규칙을 찾아 해결하는 간단한 구현문제 입니다.

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

int n, arr[100000];
vector<int> v;

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

int main() {
        int _gcd, cnt = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i++) 
                scanf("%d", &arr[i]);
        
        sort(arr, arr + n);

        for (int i = 0; i < n - 1; i++)
                v.push_back(arr[i + 1] - arr[i]);
        
        _gcd = gcd(v[0], v[1]);
        for (int i = 2; i < n; i++)
                _gcd = gcd(_gcd, v[i]);

        for (int i =0; i < n - 1; i ++)
                cnt += v[i] / _gcd - 1;
                
        printf("%d", cnt);
}

(개발 환경 : vs code)