가로수

코드

[ 나의 풀이 ]

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <deque>
#include <map>
#include <cmath>
#include <numeric>
using namespace std;
// 2485 : 1:01 ~ 1:42
// 최대 O(NlogN)
int N, ans=1e9;
int MAX=1e9, pre;
vector<int> street;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
    {
        int a;
        cin >> a;
        street.push_back(a);
        /* 나무들 간 최소 간격을 구하는 것
           --> 심을 수 있는 최대 간격이 이 최소 간격보다 클 수 없기 때문 */
        if(pre != 0)
            MAX = min(MAX, a-pre+1);
        pre = a;
    }
    sort(street.begin(), street.end());
    for(int size=MAX;size>=0;size--)
    {
        int cnt=0;
        int cur=street.front();
        for(int i=1;i<street.size();i++)
        {
            while(cur < street[i])
            {
                cnt++;
                cur += (size+1);
            }
            if(cur == street[i]) cnt--;
            else goto stop;
        }
        cout << cnt;
        return 0;
        stop:;
    }
    return 0;
}

[ 최대공약수 풀이 ]

#include <iostream> 
#include <vector> 
using namespace std;
// 최대 O(NlogN)
int N;
vector<int> v;
vector<int> tree;
int GCD(int a, int b){
    if(b==0) return a;
    else return GCD(b, a%b);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0,tmp=0;i<N;i++)
    {
        cin >> tmp;
        tree.push_back(tmp);
        /* 모든 나무 사이의 간격을 저장 */
        if(i != 0)
            v.push_back(tree[i] - tree[i-1]);
    }
    int gcd = v[0];
    /* 모든 간격 크기에 대한 최대공약수(GCD) 구하기 */
    for(int i=1;i<v.size();i++)
    {
        gcd=GCD(gcd, v[i]);
    }
    /* ans = ((시작 ~ 끝)/gcd +1) - (미리 심은 나무 개수) */
    int ans = ((tree[N-1] - tree[0])/gcd+1) - N;
    cout << ans;
    return 0;
}

• key point
  • 각 나무들 간의 간격의 크기들을 모두 구해서 모두에 대한 GCD(최대 공약수)를 구해야 함
  • ans = 심을 수 있는 나무의 수 - 미리 심은 나무의 수
  • 심을 수 있는 나무의 수 = (마지막 나무 위치 - 처음 나무 위치)/gcd + 1
    (마지막 +1은 처음 나무 개수를 세준 것!)