[백준 17087번 숨바꼭질 6 - node.js] [알고리즘 기초 1/2]

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

17087번: 숨바꼭질 6

 

문제

 

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

 

입력

 

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

 

출력

 

가능한 D값의 최댓값을 출력한다.

 

예제 입출력

 

입력	출력
3 3 1 7 11	2

 

풀이[node.js]

 

 

728x90

이번 문제는 설명이 애매해서 어떤 식으로 풀어서 결과값이 나오게 되는 건지 이해하기 어려웠습니다.

결국은 최대공약수를 구하는 문제였는데요.

만약, 동생이 한명이라면, 자신의 위치에서 동생까지의 거리를 구해서 반환해주면 됩니다.

하지만, 동생이 여러명이라면, 자신의 위치에서 각 동생까지의 거리를 구한 후, 최대공약수를 구해주어야합니다.

 

두 수의 최대공약수는 구했지만, 두 개 이상의 최대공약수를 구해야해서 당황스러웠는데요, 우선 첫번째와 두번째 값의 최대공약수를 구하고, 해당 최대공약수와 그 다음 수의 최대공약수를 구한다면 세 수의 최대공약수가 구해집니다.

그래서, gcd가 undefined일 경우에는, 이전에 최대공약수를 아직 구하지 않았다는 뜻이므로, 최대공약수 gcd를 첫번째 수, 두번째 수로 구해줍니다.

그 이후부터는 gcd가 구해져있기 때문에, 이전에 구해진 gcd 즉, 최대공약수와, 자신과 동생의 거리를 파라미터로 보내주어서 최대공약수 gcd를 구해주면 됩니다.

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().split('\n');
var num = Number(inputs[0].split(' ')[0]);
var place = Number(inputs[0].split(' ')[1]);
var splited = inputs[1].split(' ');
var answer = [];
var gcd;
if(splited.length !== 1){
    for(var i=0; i<num; i++){
        if(gcd === undefined){
            gcd = getGcd(Math.abs(splited[i] - place), Math.abs(splited[i+1] - place));
        }else{
            gcd = getGcd(gcd, Math.abs(splited[i] - place));
        }
    }
}else{
    gcd = Math.abs(splited[0] - place);
}
console.log(gcd)
var tmp;
function getGcd(a, b){
    while(b != 0){
        tmp = a%b;
        a = b;
        b = tmp;
    }
    return a;
}