[boj] 17087. 숨바꼭질 6

[boj] 17087. 숨바꼭질 6

• 문제 링크 : https://www.acmicpc.net/problem/17087
• 사용 언어 : Node.js

17087번: 숨바꼭질 6

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.
수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.
모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자. 

1. 문제 분석

 현재 위치에서 일정 위치들까지 도달하는 문제입니다.
우선 위치 중심이 아닌 거리 중심으로 생각합시다.
문제를 수학적으로 다시 써보면 $ D\: $: 한 걸음에 이동하는 거리,  $ x \: ( 0 \leq x ) $ : 걸음수 라고 할 때
$ P_1 = Dx_1 $, $ P_2 = Dx_2 $, $ P_3 = Dx_3 \: ...  $이 성립합니다.
이때 $ x $는 양의 정수 이기 때문에 $ D $는 동생들까지의 거리 $ P1, P2, P3 \: ... $들의 공약수가 됩니다.
가능한 최댓값 $ D $ 를 구하라고 하였으므로 최대공약수를 구해주면 되겠습니다.

 

최대공약수와 최소공배수

---

 

2. 솔루션

const fs = require('fs')
const [condition, siblings] = fs.readFileSync(process.platform ===
                                              'linux' ? '/dev/stdin' : 'input.txt')
                                .toString().trim().split('\n')
const [countOfSiblings, myPosition] = condition.split(' ').map(input => +input)

// 동생들의 위치들를 위치들에서 본인의 위치만큼을 빼서 동생들과의 거리로 변환해줍니다.
// 거리는 양의 정수이기 때문에 모든 동생들과의 거리를 절대값 계산 해줍니다.
const groupOfSiblingsPositions = siblings.split(' ')
                                         .map(position => Math.abs(+position -
                                                                   myPosition))

// 최대 공약수 구하는 연산
function getGCD(a, b) {
    if (b === 0) return a;
    return getGCD(b, a % b)
}

// 현재 최대공약수
let answer = groupOfSiblingsPositions[0];

// 대상 수의 개수가 3이상인 경우의 최대공약수 계산 방법 => EX) 수의 개수가 3 일 때, GCD(a,GCD(b,c)) 와 같이 GCD를
// 중첩하여 계산
for (let i = 1; i < countOfSiblings; i++) {
    answer = getGCD(answer, groupOfSiblingsPositions[i])
}

console.log(answer)

 

---

마치며

일정 횟수의 덧셈  $  D + D + D + ... D  $ 를 곱셈 형태 $ Dx $ 로 전환할 수 있는 것을 기억합시다.