[백준 / BOJ] 2485번 가로수 (Javascript / Node js)

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

2485번: 가로수

문제 해석

첫 번째 입력으로 예시를 들어보자 나무는 현재 1 3 7 13 의 위치에 존재한다.

 

현재 존재하는 나무들 사이에 나무들을 추가하여 모든 나무들의 간격이 일정하게 만들어 주는게 문제다.

 

 

위 예시에서 모든 나무들의 간격이 일정해지기 위해서는 위와 같이 5, 9, 11에 나무들을 추가적으로 심어주면 모든 나무들의 간격이 [2]로 동일해진다.

 

여기서 문제는 어떻게 [2]라는 숫자를 도출했는가이다.

 

그래서 나는 가장 먼저 나무가 심어져있는 위치 [1,3,7,13] 으로 나무 사이의 간격 [2, 4, 6] 이란 배열을 만들었다.

 

그리고 [2, 4, 6] 의 최대공약수를 구하면 최대한 간격을 넓게 사용해서(최대한 적은 나무로) 모든 나무들을 동일한 간격에 위치시킬 수 있을 것이라 생각했다. 

 

 

 

 

이제 두번째 문제는 세개 이상의 수들의 최대공약수를 구해야 한다는 점이다.

 

 

가로수의 위치를 나타내는 정수가 10억인 것을 보아 나눠지는 수들을 일일히 검사하는 방법은 반드시 시간초과가 날테니 유클리드 호제법을 사용하여 푸는 것이 출제자가 의도한 바일 것이다.

 

그런데 지난 문제들에서 배운 유클리드 호제법은 두 수의 최대공약수를 구하는 법인게 문제였다.

 

그래서 조금 더 찾아보니 A 와 B 의 최대 공약수 와 C 의 최대 공약수,

GCD( GCD ( A , B) , C ) == GCD ( A , B , C)가 성립한다는 것을 깨달았다. (GCD는 최대공약수를 구하는 함수)

 

이것도 초등학교때 배웠던 내용 같은데 기억하지 못한게 수치스럽다,,

 

 

어찌 됐든 GCD( GCD ( A , B ) , C ) == GCD ( A , B , C) 가 성립하니, GCD( GCD ( GCD ( A , B ), C ), D ) 도 가능하겠지.

 

그러니 재귀함수를 사용해 풀면 되겠다.

 

처음엔 재귀호출이 너무 많이 되어 콜스택이 꽉차버리진 않을까 걱정했지만 다행히 가로수의 수는 100,000이 안된다 하니 문제되지 않겠다.

 

---

 

로직 구현

이제 유클리드 호제법을 이용해 최대공약수를 구하는 함수를 구현하고, 이 함수를 재귀적으로 호출하여 다수의 최대공약수를 구하는 로직을 구현해보자.

let divisor = new Set([]);   // 나무 사이의 간격들이 중복값이 제거된 채 들어있는 배열 (재귀함수의 호출을 줄이기 위해)

let divisorArr = [];             // 실제 나무 사이의 간격들이 들어있는 배열

for (let i = 0; i < input.length - 1; i++) {

  divisor.add(input[i + 1] - input[i]);

  divisorArr.push(input[i + 1] - input[i]);

}

var GCD = 0; // 재귀함수에서 다루기 위해 전역으로 변수를 선언

const fcc = (big, small, index) => {

  let mod = big % small;

  while (mod > 0) {

    let tmp = mod;

    mod = small % mod;

    small = tmp;

  }

  GCD = small;

  if (index == 0) {

    return;

  } else {

    return fcc(small, divisorArr[index - 1], index - 1);

  }

};

fcc(

  divisorArr[divisorArr.length - 1],

  divisorArr[divisorArr.length - 2],

  divisorArr.length - 2

);

 

 

위의 유클리드 호제법을 구현한 함수가 이해가 되질 않는다면 앞서 포스팅한 [최소공배수] 문제 풀이를 보고 오자.

[백준/BOJ] 1934번 최소공배수 (Javascript / Node js) (tistory.com)

[백준/BOJ] 1934번 최소공배수 (Javascript / Node js)

 

이제 구한 GCD(최대공약수)를 이용해 심어줄 나무의 개수를 구하자.

두번째 7번 나무와 13번 사이에 심어진 나무의 개수를 보면, 7번 나무와 13번 나무 사이의 간격 6을 최대공약수 2 로 나누고 1을 빼주니 심어준 나무의 개수 2가 나온 것을 볼 수 있다.

 

모든 나무들의 간격들을 담은 배열을 순회하며 위 그림에서 구한 수식을 이용해 심을 나무 수들을 모두 더하면 끝이다.

 

let answer = 0;

for(let i of divisorArr){

    if(i != GCD){ // 간격이 이미 최대공약수일 경우는 패스

        answer += i/GCD - 1;

    }

}

 

 

 

전체코드

 

const fs = require("fs");

const input = fs

  .readFileSync("../input.txt")

  .toString()

  .trim()

  .split("\n")

  .map((item) => Number(item));

input.shift();

let divisor = new Set([]);

let divisorArr = [];

for (let i = 0; i < input.length - 1; i++) {

  divisor.add(input[i + 1] - input[i]);

  divisorArr.push(input[i + 1] - input[i]);

}

var GCD = 0;

const fcc = (big, small, index) => {

  let mod = big % small;

  while (mod > 0) {

    let tmp = mod;

    mod = small % mod;

    small = tmp;

  }

  GCD = small;

  if (index == 0) {

    return;

  } else {

    return fcc(small, divisorArr[index - 1], index - 1);

  }

};

fcc(

  divisorArr[divisorArr.length - 1],

  divisorArr[divisorArr.length - 2],

  divisorArr.length - 2

);

let answer = 0;

for(let i of divisorArr){

    if(i != GCD){

        answer += i/GCD - 1;

    }

}

console.log(answer);

 

 

 

오랜만에 재귀함수를 쓰려니 머리가 너무 안돌아가서 처음엔 자괴감이 들었지만

결국엔 끝까지 혼자 힘으로 풀어내서 끈기가 성장한 느낌이라 뿌듯하다 ㅎㅎ

 

-끝-