취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2485번 문제인 가로수이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/2485 

가장 작은 숫자로 나타나는 가로수의 위치부터 간격 d로 가로수를 심었을 때 모든 가로수를 만나게 하는 그러한 간격 d를 찾으면 문제를 해결할 수 있다.

그러한 간격 d는 가장 작은 숫자로 나타나는 가로수로부터의 다른 가로수들까지의 거리의 최대공약수(gcd)와 같다는 것을 알 수 있다.

이제 가장 큰 숫자로 나타나는 가로수의 위치까지 간격 d로 가로수를 심을 때 몇 그루의 가로수가 필요한지를 계산해, 이미 심어져있는 나무의 수를 제외하면 문제가 해결된다.

아래의 코드는 입력 순서대로 인접한 두 가로수 사이의 거리로 문제를 해결하고 있는데, 유클리드 알고리즘(유클리드 호제법)의 증명을 생각하면 아래의 구현도 답을 낼 것이라는 것을 간단히 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int mn, mx, N, K; cin >> N >> K;
	mn = mx = K;
	int NN = N - 1;
	int dist = 0;
	while (NN--) {
		int x; cin >> x;
		mn = min(mn, x), mx = max(mx, x);
		dist = gcd(dist, abs(K - x));
		K = x;
	}
	cout << (mx - mn) / dist - N + 1;
}