[백준] (Swift) 17087번 - 숨바꼭질6 (문제 풀이 설명, GCD알고리즘_스위프트)

문제 링크

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

17087번: 숨바꼭질 6

문제가 조금 애매하다. 도통 input과 output의 관계가 이해가 가질 않아서 문제를 이해하기 위해 인터넷을 찾아보았다. 그렇게 알아낸 사실은 아래와 같다.

• 최대공약수를 구하는 문제이다. 그 중에서도, GCD 알고리즘을 활용하여 푸는 문제이다. 
• GCD알고리즘 (유클리드 호제법)을 이해하기 위해서는 이글 을 참고했다.

▶ 근데 도대체 왜, 최대공약수가 필요할까?

초반에는 단순히 동생이 있는 위치와 내가있는 자리의 차이를 구하여, 최댓값?을 구하면되는 줄 알았다. 이렇게 풀게 되면, 예제1번 부터 output이 말이 안됐다. (인터넷을 찾아보니 거의 대부분의 모든 사람들이 왜 최대공약수를 구하는지 모르고 있고 나랑 똑같은 고민을 거쳐간 것으로 보인다.)

다양한 인터넷 글을 뒤지다가 이글 의 필자분이 정확하게 표현해 주신것을 보고, 바로 문제를 이해할 수 있었다. 문제에서 주어진 D 는 수빈이의 보폭으로 보면, 왜 최대공약수가 필요한지 알게 된다. 예를들어 예제1번으로 설명해보면, output인 2를 수빈이의 보폭으로 보면, 동생들에게 모두 찾아갈 수 있다. 

1 ㅇ 3 ㅇ ㅇ ㅇ   7 ㅇ ㅇ ㅇ  11

이렇게 보면, 3번노란색위치에 있는 수빈이는, 보폭2로 1번동생, 보폭2 * 2 로 7번까지, 또 11번까지 보폭2 * 4 로 갈 수있다. 이 값을 D 라고 출력해달라는 것이다. 

이 풀이대로보면, 수빈이와 동생들의 위치의 차를 모두 구한 뒤, 구해진 값들의 최대공약수를 구하면, 최대보폭 D가 나온다는 것이다.
뭔데 이렇게 문제가 애매모호하게 설명해놨냐... 하..

 

내가 푼 풀이(1) - 시간 초과

시간 초과가 떳다. 아무래도 시간복잡도를 줄여야할 것 같다.

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var bro = readLine()!.split(separator: " ").map { Int(String($0))! }
var distance: [Int] = []
func gcd(_ m: Int, _ n: Int) -> Int {
    if n == 0 {
        return m
    } else if m % n == 0 {
        return n
    } else {
        return gcd(n, m%n)
    }
}

for b in bro {
    distance.append(abs(input[1]-b))
    distance.sort(by: >)
}

var ans = distance[0]
for i in 1..<distance.count {
    ans = gcd(ans, distance[i])
}

print(ans)

 

내가 푼 풀이(2) - 맞았습니다!

중간에 bro 배열을 한번 sort 해주었던 것을 지우고, 마지막에 for 문을 활용하여 큰지 작은지 한번 확인해주는 과정을 추가했다. sort 메서드가 아무래도 O(nlogn) 을 가지고 있고, 배열의 길이에 따라 점점 더 길어지므로, 테스트케이스를 통과시킬때 아무래도 시간 초과가 생긴 것 같았다.

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var bro = readLine()!.split(separator: " ").map { Int(String($0))! }
var distance: [Int] = []

func gcd(_ m: Int, _ n: Int) -> Int {
    if n == 0 {
        return m
    } else if m % n == 0 {
        return n
    } else {
        return gcd(n, m%n)
    }
}

for b in bro {
    distance.append(abs(input[1]-b))
}

var ans = distance[0]
for i in 1..<distance.count {
    if ans < distance[i] {
        ans = gcd(distance[i], ans)
    } else {
        ans = gcd(ans, distance[i])
    }
}

print(ans)

 

 

다양한 수학적 알고리즘에 대한 개념공부가 필요할 것 같다. 최대공약수를 구하는 문제인걸 알지만, gcd 알고리즘을 몰라서 인터넷을 찾아보고 풀었다. 재귀를 활용한 gcd알고리즘, 기억하자.