가로수 (feat. 백준, 2485번)

가로수
https://www.acmicpc.net/problem/2485

2485번: 가로수

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int gcd(register int a, register int b){
    return a % b ? gcd(b, a % b) : b;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, arr[100000], ans = 0;
    cin >> N;
    for(register int n = 0; n < N; ++n)
        cin >> arr[n];
    register int t = gcd(arr[2] - arr[1], arr[1] - arr[0]);
    for(register int i = 2; i < N - 1; ++i)
        t = gcd(t, arr[i + 1] - arr[i]);
    for(register int i = 0; i < N - 1; ++i)
        ans += (arr[i + 1] - arr[i]) / t - 1;
    cout << ans;
    return 0;
}
// *&)*@*

 

 

1. [1,5,11]이 있다고 했을때, 1-5는 4의 차이를 5-11은 6의 차이를 갖기 때문에 4와 6의 최대공약수(gcd)를 구해줍니다.
2. 이렇게 모든 두 가로수간 거리에 대해 최대공약수를 구했을때, 모든 가로수간 거리 / 최대공약수값 - 1의 누적합이 필요한 가로수의 개수가 되게 됩니다.