문제
출처 : www.acmicpc.net/problem/17087
수빈이가 동생'들'과 숨바꼭질을한다.
선영이는 +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
'알고리즘 (2020 : 08 : 10 ~ ) > 수학' 카테고리의 다른 글
[백준 / BOJ] 1393 음하철도 구구팔 (Java) (0) | 2021.05.02 |
---|---|
[백준 / BOJ] 1256 사전 (0) | 2021.04.04 |
[백준 / BOJ] 1629 곱셈 (0) | 2020.08.25 |
[백준 / BOJ] 1241 머리 톡톡 (0) | 2020.08.19 |
[백준 / BOJ] 1105 팔 (0) | 2020.08.19 |