PS
-
백준) 17087 - 숨바꼭질6 (C++)PS/BOJ 2023. 11. 19. 19:16
문제 링크 : https://www.acmicpc.net/problem/17087 문제 설명 SSS = 수빈이의 위치DDD = 보폭AnA_nAn = n번째 동생의 위치 DDD씩 이동해서 모든 동생의 위치에 도착할 수 있어야 한다. 문제 풀이D씩 이동해서 모든 위치를 방문할 수 있으려면 D는 이동할 거리들의 최대 공약수가 되어야 한다.이동할 거리가 D로 나눠져야 해당 위치로 정확히 이동할 수 있기 때문이다.예) gcd(8, 16, 6) = 2 두 거리의 최대 공약수를 구하고, 그렇게 구한 최대 공약수와 다음 거리의 최대 공약수를 구해가는 방식으로전체 거리의 최대 공약수를 구할 수 있다. 최대공약수를 구하는 알고리즘인 유클리드 호제법 사용.https://ko.wikipedia.org/wiki/유클리..