[C++] 백준 2485번 가로수

1. 문제이해

2485번: 가로수 (acmicpc.net)

2485번: 가로수

 

이미 심어져있는 가로수의 개수와 각 가로수들이 심어진 위치가 주어진다.

모든 가로수들이 심어진 간격이 동일하게 되도록 가로수들을 추가로 심으려고 할 때,

추가로 심어야 하는 가로수들은 몇 그루인지 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

이미 심어져있는 가로수들 사이의 간격을 고려해,

모든 가로수들 사이의 간격이 같아지도록 가로수들을 심을 때,

최소 몇 그루를 더 심어야 하는지를 구하는 문제이다.

 

그림을 통해 아래 예제 1의 경우를 보자.

글보다는 그림으로 설명하는게 더 좋을 것 같아서 이번에도 직접 작성해보았다.😤

위의 그림에서 나타낸 것 처럼, 풀이 방법은 다음과 같다.

 

1. 가로수들 사이의 간격을 구하고

2. 간격들의 최대공약수를 구하고

3. (간격 / 최대공약수) - 1 해준 뒤 모두 더한다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int tree[100000];
int tree_distance[100000];

// 최대공약수를 구하는 함수 (유클리드 호제법)
int Euclidean(int a, int b) {
	int r = a % b;
	if (r == 0)
		return b;
	else
		return Euclidean(b, r);
}

int main() {
	int N;	// 가로수의 개수
	int gcd = 0;	// 가로수의 간격들의 최대공약수
	int count = 0;	// 가로수를 추가로 몇번 심어야 하는지

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tree[i];
	}

	// 가로수들을 거리 순으로 정렬
	sort(tree, tree + N);

	// 가로수들 사이의 간격 구하기
	for (int i = 0; i < N - 1; i++) {
		tree_distance[i] = tree[i + 1] - tree[i];
	}

	// 가로수들의 간격의 최대공약수 구하기
	gcd = tree_distance[0];
	for (int i = 1; i < N - 1; i++) {
		gcd = Euclidean(gcd, tree_distance[i]);
	}

	// 가로수들 사이의 간격을 최대공약수로 나누어
	// 몇개를 추가로 심어야 하는지 구하기
	for (int i = 0; i < N - 1; i++) {
		// 양끝에 이미 하나씩 심어져 있으므로 -1
		count += (tree_distance[i] / gcd) - 1;	
	}

	cout << count;

	return 0;
}

코드는 길어보이지만, 원리는 위에서 봤던 것 처럼 간단하다.

가로수의 개수(N)와 각 가로수들의 위치(tree[i])를 입력받은 후,

가로수들 사이의 간격(tree_distance[i])을 따로 배열에 저장한다.

 

이후 가로수들의 간격의 최대공약수(gcd)를 구해줬는데,

최대공약수를 구하는 방법은 따로 유클리드 호제법 함수(Euclidean)를 구현해 구해주었다.

최대공약수와 최소공배수를 구한 코드가 이전 포스팅에 있으니 참고하자.

(해당 포스팅에서는 2개의 숫자를 입력받고, 이번에는 N개의 숫자를 입력받았는데,

위 소스코드처럼 for문을 이용해주면 N개도 동일한 방법으로 최대공약수를 구할 수 있다.)

 

https://beginnerdeveloper-lit.tistory.com/2

[C] 백준 2609번 최대공약수와 최소공배수

 

최대공약수를 구한 뒤에는, ( 가로수들 사이의 거리 / 최대공약수 ) -1

을 해주어, 해당 값들을 모두 더해주었다.

 

 

---

오늘은 왠지 느낌이 좋아서 2문제를 풀어보았다.😊

사실 SQLD 공부를 하기 싫어서이기도 하다..ㅎㅎㅎ

SQLD 시험이 얼마 남지 않았는데.. 남은 기간이라도 열심히 해야지..😂