가로수
코드
[ 나의 풀이 ]
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <cmath>
#include <numeric>
using namespace std;
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
은 처음 나무 개수
를 세준 것!)