백준/실버
[백준 2485번] 가로수 (C++)
게임개발기원
2025. 3. 27. 03:51
문제링크 : http://acmicpc.net/problem/2485
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
int arr[100001];
vector<int>v;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for(int i=0; i<N; i++) cin >> arr[i];
for(int i=0; i<N-1; i++)
{
v.push_back(arr[i+1] - arr[i]);
}
int tmp = v[0];
for(int i=1; i<v.size(); i++) tmp = gcd(tmp, v[i]);
int result = 0;
for(int i=0; i<v.size(); i++) result += (v[i]/tmp-1);
cout << result;
return 0;
}
최대공약수를 활용한 문제이다.
각 거리의 간격을 살펴보면 다음과 같다.
1 3 7 13
간격 : 2, 4, 6 (필요 0개, 1개, 2개)
각 간격의 최대 공약수를 구하면 2다.
필요 갯수를 살펴보면 해당 간격/최대공약수 - 1을 하면 각 간격의 필요 개수인 것을 알 수 있다.