백준17887 - 숨바꼭질 6 (유클리드 호제법) node.js

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

 

문제 해결 방식

수빈이가 자신의 위치 기준, +D 혹은 -D로만 이동할 수 있다는 점에서 해결 방식을 찾았다.

만약 수빈이의 위치가 0, 동생들의 위치가 [2,8]라면

2 * 1 로 2로 이동, 2 *4 로 8로 이동할 수 있기 때문에 이때 2는 모든 동생을 찾을 수 있는 값이 된다.

그리고 이 값은 2와 8의 최대공약수.

 

따라서, 수빈이 위치를 기준으로 동생들의 거리를 구한 뒤 동생들의 거리의 최대공약수를 구하면 된다.

이때 이 최대공약수를 구하는 알고리즘은 유클리드 호제법을 활용하면 되는데, 

유클리드 호제법이란 두 개의 정수를 나누어가며 최대공약수를 찾는 방식이라고 말할 수 있다.

 

전체 소스 코드

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

function solution(data) {
  const [[_, M], list] = data.map((el) => el.split(" ").map(Number));
  const arr = list.map((el) => (M - el >= 0 ? M - el : -M + el));
  let result = arr.shift();

  arr.forEach((el) => (result = getGCD(result, el)));

  console.log(result);
}

function getGCD(x, y) {
  let [a, b] = [Math.max(x, y), Math.min(x, y)];

  while (b > 0) {
    const temp = a % b;
    a = b;
    b = temp;
  }

  return a;
}

solution(input);