백준 1508 - 레이스 - swift

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

1508번: 레이스

 

 

주어진 조건을 보면 심판들은 정해진위치에만 서있을 수 있다. 

정해진위치( K )의 개수는 최대 50개이다. 

그렇지만 심판들( M )의 개수는 최대 만개이다. 

 

여기서 알수있는 사실은, M이 K보다 크거나같다면, 무조건 특정위치에 여러명의 심판들이 존재할수밖에 없다는 사실이다.

이 경우에 답은 무조건 1로 채워진 문자열이여야할 것 이다. 

 

여기서 어떻게 접근해야할까, 

정해진위치를 조합으로 모두 탐색해야할까? 

50C25 는 126410606437752개이다.

이 수없이많은 경우의수를 모두 탐색하기에는 시간초과다.

 

그러므로 더 효율적인 방법을 생각해야한다. 

 

대체로 이런문제들은 자주접하다보면 이분탐색으로 풀 수 있다는것을 알 수 있다.

최대 거리는 백만이므로, 0부터 백만까지 이분탐색을통해서 mid를 정하고, 

이 mid를 가장 가까운 두 심판사이의 거리라고 미리 정하고 시작한다. 

그래서 각 위치들을 탐색하면서,최소간격이 mid보다 크면서 모든 심판들을 세울 수 있다면 ? 

mid를 조금더 키워서 이분탐색을 다시해본다. 

 

문제에서 답이여러개인경우에는 사전순으로가장 늦은 답부터 출력하라했으니, 

위치들을탐색할때 앞에서부터 차례대로 탐색하고, 조건이 모두 일치하면 바로 break로 탈출하면된다. 

이 경우에 이 답이 가장 늦을 수밖에없다. 

 

 

let q = readLine()!.split(separator: " " ).map{Int(String($0))!}
let N = q[0], M = q[1], K = q[2]
let list = readLine()!.split(separator: " " ).map{Int(String($0))!}

if M >= K {
    print(String(repeating: "1", count: K))
} else {
    var l = 0, r = N
    var ans = [Int]()
    while l<=r {
        let mid = (r+l)/2
        var dist = 0
        var check = [0]
        for i in 1..<K {
            if list[i]-list[dist] >= mid {
                dist = i
                check.append(i)
            }
            if check.count == M {
                break
            }
        }
        if check.count == M {
            l = mid+1
            ans = check
        } else {
            r = mid-1
        }
    }
    var tempt = Array(repeating: "0", count: K)
    ans.forEach{tempt[$0] = "1"}
    print(tempt.joined())
}