[백준 2485] 가로수 (C#, C++) - soo:bak

문제 링크

2485번 - 가로수

설명

이미 심어진 가로수들 사이에 나무를 추가로 심어서 모든 간격을 같게 만들 때, 최소 몇 그루를 심어야 하는지 구하는 문제입니다.

접근법

모든 간격을 같게 만들려면 새로운 간격이 기존 모든 간격의 약수여야 합니다. 간격이 작을수록 더 많은 나무를 심어야 하므로, 최소 개수를 원한다면 가능한 가장 큰 간격을 선택해야 합니다. 이 값은 기존 간격들의 최대공약수입니다.

먼저 인접한 가로수 사이의 거리들을 모두 구합니다. 이 거리들의 최대공약수를 구하면 새로운 간격이 됩니다.

이후 각 구간마다 필요한 나무 수를 계산합니다. 거리가 d이고 새 간격이 g라면, 그 구간에는 d/g - 1 그루의 나무를 추가로 심어야 합니다. 모든 구간에 대해 이 값을 합산하면 정답입니다.

---

Code

C#

using System;

class Program {
  static long Gcd(long a, long b) {
    while (b != 0) {
      var t = a % b;
      a = b;
      b = t;
    }
    return a;
  }

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var pos = new long[n];
    for (var i = 0; i < n; i++) pos[i] = long.Parse(Console.ReadLine()!);

    var g = pos[1] - pos[0];
    for (var i = 1; i < n - 1; i++)
      g = Gcd(g, pos[i + 1] - pos[i]);

    var add = 0L;
    for (var i = 0; i < n - 1; i++)
      add += (pos[i + 1] - pos[i]) / g - 1;

    Console.WriteLine(add);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;

ll gcd(ll a, ll b) {
  while (b) {
    ll t = a % b;
    a = b;
    b = t;
  }
  return a;
}

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

  int n; cin >> n;
  vl x(n);
  for (int i = 0; i < n; i++) cin >> x[i];

  ll g = x[1] - x[0];
  for (int i = 1; i < n - 1; i++)
    g = gcd(g, x[i + 1] - x[i]);

  ll ans = 0;
  for (int i = 0; i < n - 1; i++)
    ans += (x[i + 1] - x[i]) / g - 1;

  cout << ans << "\n";

  return 0;
}