Algorithm/Algorithms Practice
[BOJ/C++] 가로수(2485번)
Patrick_
2022. 10. 24. 15:16
1. 개요
https://www.acmicpc.net/problem/2485
2485번: 가로수
첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가
www.acmicpc.net
1-1. 설명
가로수가 임의의 간격으로 심어져 있다. 우리는 가로수들이 모든 간격이 동일하게 되도록 가로수를 추가로 심게끔 추진한다. 최대한 적은 가로수의 수로 같은 간격이 되도록 할때, 심어야 할 최소의 가로수 수를 구하는 프로그램을 작성한다.
1-2. 제한 사항
- 첫 줄에는 이미 심어져있는 가로수의 수를 나타내는 정수 N이며, 3이상 100,000 이하 정수
- 둘째 줄부터 N개의 줄에는 심어져 있는 가로수 위치가 주어지며, 위치는 1,000,000,000 이하
2. 구현
2-1. 풀이
주어진 가로수의 간격을 구한 후, 그 수들의 최대 공약수를 구하여 최대 공약수 간격만큼 가로수의 수를 세어주었다. 조금만 생각하면 최대공약수라는 답을 찾을 수 있었다.
2-2. 코드
#include <iostream>
using namespace std;
constexpr size_t MAX_NUM = 100000;
int nums[MAX_NUM];
int gap[MAX_NUM];
int gcd(int a, int b);
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, num = 0, result = 0;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> nums[i];
if (i == 0) continue;
gap[i] = nums[i] - nums[i - 1];
}
// 각 간격의 최대 공약수를 구해줌
num = gap[0];
for (int i = 1; i < N; i++) {
num = gcd(num, gap[i]);
}
int index = 0;
for (int i = nums[0]; i < nums[N - 1]; i += num) {
if (i == nums[index]) index += 1;
else result += 1;
}
cout << result;
return 0;
}
int gcd(int a, int b) {
if (a == 0) return b;
return gcd(b % a, a);
}