백준 2485번 가로수 (javascrit, node.js, 자바스크립트, 노드)

문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.
편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.
예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.
심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.

출력

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

예제입력 1

4
1
3
7
13

예제출력 1

3

예제입력 2

4
2
6
12
18

예제출력 2

5

문제풀이

균등하게 가로수가 심어지도록 해야하는 프로그램 구현
주어진 가로수의 위치(입력값)를 보고 같은 간격으로 가로수가 심어지도록 계산해야 함
예제를 보면 1,3,7,13의 위치에 있다면 (5,9,11)의 위치에 심어야 하는데
1부터 3까지의 거리 2, 3부터 7까지의 거리는 4, 7부터 13까지의 거리는 6 이므로 거리의 최대 공약수를 구하면 2이므로 2칸마다 심어짐
추가되는 개수를 구하려면 두 가로수 사이의 거리 / 최대공약수 -1로 계산해야 함(사실 나도 다른 사람의 글보고 이해함 ㅠ)

// 2485번 가로수

// 주어진 가로수의 위치(입력값)를 보고 같은 간격으로 가로수가 심어져야하는 가로수의 최소수 구해야함
// 추가 되는 나무는 기존의 나무들 사이에 심어야 함

// 예로 1,3,7,13 의 위치에  있다면 (5,9,11)의 위치에 심어야하는데
// 1~3 까지의 거리 2, 3~7 까지의 거리는 4, 7~13까지의 거리는 6 이므로 최대공약수는 2
// 추가 되는 갯수 = 두 가로수 사이의 거리 /최대공약수 -1

const fs = require("fs");
const file = process.platform === "linux" ? "dev/stdin" : "./text.txt";
const input = fs.readFileSync(file).toString().trim().split("\n");

input.shift(0);

// 최대 공약수 구하는 식
const gcd = (a, b) => {
  if (b === 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
};

// 가로수 사이의 거리
const distance = [];
for (let i = 0; i < input.length - 1; i++) {
  distance.push(input[i + 1] - input[i]);
}

// 가로수 사이의 거리 최대공약수
// distgcd 변수 가로수사이의 거리를 구하기 위해 첫 번째 가로수 사이로 변수 설정
let distgcd = distance[0];
for (let i = 0; i < distance.length - 1; i++) {
  distgcd = gcd(distgcd, distance[i]);
}

// 가로수 사이에 추가되는 부분 계산
let result = 0;
for (let i = 0; i < distance.length; i++) {
  // 가로수 사이의 거리가 최대공약수랑 같지 않은 것만 계산
  if (distance[i] !== distgcd) {
    result += distance[i] / distgcd - 1;
  }
}

console.log(result);