[BOJ/C++] 가로수(2485번)

1. 개요

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

2485번: 가로수

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);
}