백준-약수, 배수와 소수 2485 가로수

가로수

주어진 자료에서 거리를 측정하여 최소 간격을 찾아 비어있는 부분에 추가로 자료를 넣어 같은 간격으로 채우기

제약사항

• 2 < N(Input Size) <= 100,000
• 0 < InputCase <= 1,000,000,000
• There is No Duplicate

주의 사항

없다.

CPP풀이

가로수_2485.cpp

/**
 * 백준 가로수_2485
 * 주어진 자료에서 거리를 측정하여 최소 간격을 찾아 비어있는 부분에 추가로 자료를 넣어 같은 간격으로 채우기
 * 
 * 제한사항
 *****************************************
 * 2 < N(Input Size) <= 100,000          *
 * 0 < InputCase <= 1,000,000,000        *
 * There is No Duplicate                 *
 *****************************************
 *
 *
 *
 * 주의
 * 없다.
 * 
 * 풀이시간 60분
 */


#include <iostream>
#include <algorithm>

using namespace std;

static int arr[100000];
static int dist[100000];

int GCD(int a, int b);
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;

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

    sort(arr, arr + N);

    
    // 거리 차이 찾기
    for (int i = 0; i < N-1; ++i)
    {
        dist[i] =  arr[i+1] - arr[i];
    }
    
    int minDist = dist[0];
    for (int i = 0; i < N-1; ++i)
    {
        minDist = GCD(minDist, dist[i]);
    }
    
    int count = 0;
    for (int i = 0; i < N-1; ++i)
    {
        count += (dist[i] / minDist) -1;
    }
    cout << count << '\n';
    return 0;
}

int GCD(int a, int b)
{
    while(b != 0)
    {
        int temp = a % b;
        a = b;
        b= temp;
    }
    return a;
}

모든 예제 코드의 소스파일은 제 개인 깃허브 레포지토리에 있습니다.

Workspace/알고리듬 풀이 at main · cyphen156/Workspace · GitHub

Workspace/알고리듬 풀이 at main · cyphen156/Workspace