백준 BOJ 2485 - 가로수

이 문제의 핵심은 최대공약수이다.

이걸 중학교 2학년때 풀었던거같은데

그때 한참걸렸던걸

지금 몇분만에 풀어내는걸 보니

참 감회가 새롭다.. ㅋㅋ

 

가장 먼 나무 - 가까운 나무로

길이를 구하고,

최대공약수로 나눠준 다음

가장 끝에 +1 해줘서 나무의 전체 수를 구한다.

그다음 입력된 나무의 수인 N을 빼주면

우리가 원하는 답을 찾을 수 있다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;
typedef long long int ll;

int input[123456] = {0};
int arr[123456]   = {0};

ll gcd(ll a, ll b){
	while(b!=0){
		ll r = a%b;
		a = b;
		b = r;
	}
	return a;
}

int main(){
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++) scanf("%d", &input[i]);
	
	sort(input, input+n);
	for(int i=1; i<n; i++){ arr[i] = input[i]-input[i-1]; }
	for(int i=2; i<n; i++){ arr[i] = gcd(arr[i], arr[i-1]); }
	
	printf("%d", (input[n-1]-input[0])/arr[n-1]-n+1);
	return 0;
}

arr[]는 최대공약수를 구하기 위해 나무 간의 거리를 저장해두기도 하고,

그 나무들의 최대공약수를 구할때도 사용되는 배열이다.