[백준 / BOJ] 17087 숨바꼭질 6

문제

출처 : www.acmicpc.net/problem/17087

17087번: 숨바꼭질 6

수빈이가 동생'들'과 숨바꼭질을한다. 

선영이는 +D, -D만큼 이동할수있다. 선영이의 위치와 동생들의 위치가 주어졌을때, 선영이가 모든 동생을 찾을수있는 최대 D값을 찾는문제다.

 

풀이

수학문제다.

 

선영이는 모든 동생을 찾아야한다. 선영이는 항상 +D, -D만큼 움직일수있으므로, 모든 동생과의 거리차들의 최대공약수만큼 움직여야 모든동생들을 찾을수있다.

 

1. 선영이의 위치와 모든동생들의 위치를 벡터에 집어넣고 정렬한다.

2. 벡터의 (idx+1) - (idx) 의 거리차를 num벡터에 집어넣는다.

3. num벡터의 원소가 1개만남을때까지 모든 정점들의 최대공약수를 구하면 된다.

 

이때, 1 2 3 4 ... 이런식으로 나눠서 구하면 시간초과가 나기때문에 (동생이 최대 1억까지 갈수있으므로) 유클리드 호제법을 이용하여 빠르게 구해야한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88%206/main.cpp

devxb/JJUNalgo