[백준JS] 2485. 가로수

안녕하세요. 박기린 입니다.

백준 2485번 가로수 문제를 풀어봅시다.

 

 

문제 링크

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

 

 

 

---

문제 해석

1, 3, 7, 13에 가로수가 놓여 있다고 가정을 합니다.

문제의 목표는, 보기로 주어진 일정하게 놓이지 않은 가로수 사이에 최소한의 가로수를 놓아서 일정한 거리를 두게 끔 만드는 것입니다.

 

방법은 정말 간단합니다. 각 가로수 간의 거리를 구한 후, 그 거리들의 최대공약수를 구하면 됩니다.

최대공약수의 거리가 되게 끔 가로수를 사이에 넣어주면, 최소한의 가로수를 놓아서 일정한 거리를 두게 만들 수 있습니다.

 

 

 

 

가로수가 놓이는 갯수는

두 가로수 사이에 추가되는 가로수 갯수 = 두 가로수 사이의 거리 / 최대공약수 - 1

입니다.

 

3과 7 사이에는 4 / 2 - 1로 1개의 가로수가,

7과 13 사이에는 6 / 2 - 1로 2개의 가로수가 추가됩니다.

 

 

 

---

정답 코드

const fs = require("fs");
const [count, ...strInput] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const input = strInput.map(Number);

const getGcd = (x, y) => {
  if (y == 0) return x;
  else return getGcd(y, x % y);
};

const dist = [];
for (let i = 0; i < count - 1; i++) {
  dist.push(input[i + 1] - input[i]);
}

let gcd = input[count - 1];
for (let i = 0; i < count - 2; i++) {
  let tempGcd = getGcd(dist[i + 1], dist[i]);
  if (tempGcd < gcd) gcd = tempGcd;
}


let output = 0;

for (let i = 0; i < count - 1; i++) {
  const tempDis = dist[i];

  if (tempDis !== gcd) {
    output += tempDis / gcd - 1;
  }
}

console.log(output);

 

 

 

---

정답 코드 풀이

const getGcd = (x, y) => {
  if (y == 0) return x;
  else return getGcd(y, x % y);
};

유클리드 호제법으로 두 수 간의 최대공약수를 구하는 함수를 선언합니다.

 

 

 

const dist = [];
for (let i = 0; i < count - 1; i++) {
  dist.push(input[i + 1] - input[i]);
}

dist는 distance를 의미합니다.

for 반복문을 이용해서 가로수 간의 거리를 구한 후, dist Array에 push() 합니다.

 

 

 

let gcd = input[count - 1];
for (let i = 0; i < count - 2; i++) {
  let tempGcd = getGcd(dist[i + 1], dist[i]);
  if (tempGcd < gcd) gcd = tempGcd;
}

gcd(greatest common divisor)는 최대공약수를 의미합니다.

우선, 가장 멀리 위치한 가로수를 gcd로 초기 설정합니다.

for 반복문을 통해 dist Array에 있는 거리들의 tempGcd(임시 최대공약수)를 구합니다.

tempGcd가 gcd보다 작을 경우, gcd를 tempGcd로 재설정합니다.

 

 

 

let output = 0;

for (let i = 0; i < count - 1; i++) {
  const tempDis = dist[i];

  if (tempDis !== gcd) {
    output += tempDis / gcd - 1;
  }
}

console.log(output);

구한 최대공약수를 이용해서 가로수 놓기를 할 차례입니다.

for 문을 이용해서 각 가로수 간의 거리가 담긴 distArray에 접근합니다.

 

만약 거리의 길이가 gcd와 같다면 pass,

다르다면 

두 가로수 사이에 추가되는 가로수 갯수 = 두 가로수 사이의 거리 / 최대공약수 - 1

위의 식을 적용해서 계산한 후, output 변수에 더합니다.

그리고 ouput 변수를 출력합니다. 그러면 끝입니다.