[C/C++ 백준 2485번] 가로수 (Silver 4)

 

#include <cstdio>
#include <algorithm>
using namespace std;
long long int gcd(long long int a, long long int b){
	return b ? gcd(b, a%b) : a;
}
int main(void){
	long long int N, array[100001], maxi = -1;
	scanf("%lld", &N);
	scanf("%lld", &array[0]);
	for(int i=1; i<N; i++){
		scanf("%lld", &array[i]);
		array[i] -= array[0];
		maxi = max(array[i], maxi);
	}
	long long int ans = gcd(array[1], array[2]);
	for(int i=3; i<N; i++){
		ans = gcd(array[i], ans);
	}
	printf("%d", maxi/ans-(N-1));
}

www.acmicpc.net/problem/2485

2485번: 가로수

첫번째 가로수부터 해당 간격마다 나무를 심을 때, 이미 심어져 있는 가로수를 포함해야 한다.

즉 첫번째 가로수부터의 거리 x마다 나무를 심는다면, 나머지 가로수들과의 거리가 모두 x의 배수여야한다.

모든 나무에서 첫번째 가로수의 거릴 빼주고, 최대공약수를 구해 나무를 심어주자.

 

유클리드 호제법을 이용한다면 최대공약수를 쉽게 구할 수 있다.