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

백준 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);