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

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

2485번: 가로수

 

해결 방법

  

   확실히 생각을 오래 하니까 쉬워졌다. 

간격을 전부 구해서 배열에 저장한 후 최대공약수를 구해주고 간격을 최대공약수로 나눈 뒤 -1 만큼 해준 숫자를 모두 더해주면 된다.

ex) 1 3 7 13

        2  4  6    // 간격

        1  2  3    // 최대공약수 2로 나눔

        0  1  2    // -1 해준다.

        답 : 3

 

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

long long int euclid(long long int a, long long int b)
{
    if (a % b != 0)
    {
        return euclid(b, a % b);
    }
    else
    {
        return b;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  
     
    int N;

    cin >> N;

    int* arr = new int[N]();
    int* itv = new int[N-1]();

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

    for (int i = 0; i < N - 1; i++)
        itv[i] = arr[i + 1] - arr[i];

    int max_div = euclid(itv[0], itv[1]);
    
    for (int i = 1; i < N - 2; i++)
        max_div = euclid(max_div, itv[i + 1]);


    int sum = 0;

    for (int i = 0; i < N - 1; i++)
        sum += itv[i] / max_div-1;

    cout << sum;

    delete[] arr;
    delete[] itv;


    return 0;
}