알고리즘 문제(Swift) 백준 - 17087 (숨바꼭질 6)

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

​

 

수빈이의 위치 X일 때 1초에 D씩 이동해서 모든 동생을 찾아야 된다

수빈이의 위치에서 동생들의 위치(A1, A2 … An)의 차는 수빈이와 동생들 사이의 거리를 뜻함

따라서, 수빈이가 이동해야 하는 거리의 최대 공약수를 구하는 문제!

 

모든 동생들과의 거리에서 최대 공약수를 구해야 하기 때문에 재귀함수를 사용함

 

let NS = readLine()!.split(separator: " ").map{Int($0)!}
let (N, S) = (NS[0], NS[1]) // N: 동생 수, S: 수빈 위치

var A = readLine()!.split(separator:  " ").map{Int($0)!} // 동생들 위치

A = A.map{abs($0 - S)} // 수빈이가 이동해야 할 거리 (수빈 위치와 동생들 위치의 차)

// 유클리드 알고리즘
func gcd(_ a: Int, _ b: Int) -> Int {
    return a % b == 0 ? b : gcd(b, a % b)
}

// 수빈이가 이동해야 할 모든 거리의 최대 공약수를 구해야 하기 떄문에 재귀함수 사용
// value: 최대 공약수 값
func recur(index: Int, value: Int) {
    if index == N {     // 깊이가 동생의 수 N 과 같으면 종료
        print(value)
        return
    }
    
    recur(index: index + 1, value: gcd(value, A[index])) // 이전 거리들의 최대 공약수(value)와 새로운 거리의 최대 공약수(A[index])를 계산
}

recur(index: 0, value: A[0]) // value 값은 최대 공약수가 되어야 하므로 첫번째 값으로 넣어줌