(백준/C++) 2485_가로수

2485번: 가로수 (acmicpc.net) 문제는 모든 가로수 간의 간격을 같게 만들기 위해서는 가로수를 어떤 간격으로 심어야 하는지를 묻는 문제입니다.

접근법

모든 간격을 동일하게 만들기 위해서는 공통의 간격을 찾아야 합니다. 이때, 가장 적게 심을 수 있는 공통 간격을 찾는 것이 중요합니다.

공통 간격을 찾는다는 것은 달리 말하자면, 현재 심어진 가로수 간의 간격들의 공통점을 찾는 것입니다.

다시 말해, 간격들을 공통으로 나눌 수 있는 수를 찾으면, 공통 간격을 찾을 수 있다는 것입니다.

이때, 가로수를 가장 적게 심을 수 있는 공통 간격을 찾으므로, 최대 공약수(GCD)를 사용하면 쉽게 해결할 수 있습니다.

최대 공약수(GCD)는 아래 글에서 확인할 수 있습니다.

유클리드 호제법과 최대 공약수(GCD), 최소 공배수(LCM)

간단하게 정리하자면,

1. 현재 가로수 간의 간격 찾기.
2. 간격들에 대한 공통 간격 찾기.
   • 이때, 가로수를 가장 적게 심을 수 있는 공통 간격을 찾으므로 최대 공약수(GCD)를 사용.
3. 공통 간격을 찾았다면, 첫 가로수 위치부터 마지막 가로수 위치까지 가로수를 심되, 이미 심어진 가로수 수를 제외한다.

풀이

최대 공약수(GCD)에 대한 알고리즘은 유클리드 호제법 글을 참조하시면 될 것 같습니다.

아래 코드는 각 간격에 대한 최대 공약수를 찾고, 처음 가로수 위치부터 마지막 위치까지 심어야 할 총 가로수의 개수를 구합니다.

이후, 현재 심어져 있는 가로수의 수를 빼면, 간단하게 심어야 하는 가로수의 수가 나옵니다.

#include <cstdio>
#include <cstdlib>

// 1. 같은 간격
// 2. 가능한 한 적은 수

int GCD(int a, int b)
{
	while (b != 0)
	{
		int tmp = a % b;
		a = b;
		b = tmp;
	}

	return a;
}

int main()
{
	int num = 0;
	int trees[100000] = { 0, };
	int distance = 0;
	
	scanf("%d", &num);

	for (int i = 0; i < num; i++)
	{
		scanf("%d", &trees[i]);
	}

	// 첫 트리 사이의 거리를 저장한다.
	distance = trees[1] - trees[0];

	// 이후, 각 트리 사이의 간격에 대한 최소 공배수를 찾는다.
	for (int i = 2; i < num; i++)
	{
		distance = GCD(distance, trees[i] - trees[i - 1]);
	}

	// 필요한 나무 수는 심어야 할 거리에 심어야 할 나무의 수를 구한 뒤, 현재 심어진 나무 수를 빼면 된다.
	int totalTrees = ((trees[num - 1] - trees[0]) / distance) + 1;
	int needTrees = totalTrees - num;

	printf("%d", needTrees);
}

---

참고

유클리드 호제법과 최대 공약수(GCD), 최소 공배수(LCM)