[ 백준 ] 2485 / 가로수

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
34/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2485 / 가로수
 *
 * Kind :: Math
 *
 * Insight
 * - 모든 가로수가 같은 간격이 되어야 한다
 *   + 가로수들간의 간격의 최대공약수를 구해야 한다
 *     # 그래야만 이미 심어져있는 가로수들 사이에
 *       최소 개수의 가로수를 추가해서
 *       모든 가로수를 같은 간격으로 심을 수 있다
 *       -> 즉, 새로 심어야 하는 가로수의 최소수는
 *          가로수들간의 간격의 최대공약수 만큼의 간격을 두고
 *          심었을 때, 새로 심어지는 가로수의 개수이다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int P[N];
    for (int i=0; i<N; i++)
        cin >> P[i];

    // Process
    sort(P, P+N); /* 가로수의 위치를 오름차순으로 정렬 */
    int dst = P[1]-P[0];
    /* 심어져 있는 가로수들 간 간격들의 최대공약수를 구함 */
    for (int i=2; i<N; i++) {
        dst = gcd(dst, P[i]-P[i-1]);
    }
    /* 심어야 하는 전체 가로수의 개수 - 이미 심어져 있는 가로수의 개수 */
    int ans = (P[N-1]-P[0])/dst+1-N;

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글