백준 2110 공유기 설치

출처: www.acmicpc.net/problem/2110

분류: 이분 탐색

---

접근방식

이분 탐색 문제인 걸 알고 접근했는데도 접근이 어려웠던 문제였습니다. ㅠㅠ 이녀석 쉬워지질 않네요...

공유기들의 위치가 주어지기 때문에 이걸 가지고 어떻게 이분탐색을 해야하나 싶지만, 저희는 공유기 사이의 거리가 가장 큰 경우를 찾아야 합니다. 따라서 공유기 사이의 거리를 가지고 이분 탐색을 돌려야 합니다.

따라서 저희는

최소 설치 거리를 low

최대 설치 거리를 high 

정해서 이분탐색을 해야합니다.

다음에는 해당 거리를 최소 간격으로 해서 공유기를 설치할 수 있는지 없는지만 체크해주면 됩니다. 이건 일단 나중에 생각해보죠 :(

 

자 그럼 공유기 사이의 거리가 가장 짧은 경우는 어떤 경우일까요?
바로 옆집에 공유기를 설치했을 경우 입니다. 따라서 low = 1 로 고정시킬 수 있습니다.

가장 긴 경우는 어떤 경우일까요?
가장 멀리 떨어진 두 집이 최대가 되겠네요! 

예를 들어 살펴보겠습니다. 문제의 예시 그대로 [ 1 2 4 8 9 ] 를 가지고 생각해볼게요.

우선 low는 1로 하기로 했습니다. 

high는 가장 멀리 떨어진 두 집 사이의 거리가 되므로 여기선 9 - 1 = 8 이 되겠네요.

이제 low와 high가 정해졌으니 이분탐색을 돌리는거에요.

가장 먼저 8과 1의 mid인 4를 탐색하겠죠? 만약 최소 거리가 4이상으로 공유기 설치가 가능하다면
최대 거리를 4로 갱신해주고,
더 큰 거리로 가능한지 확인하기 위해서 low를 mid+1인 5로 바꿔줘서 5와 8 사이에서 더 큰 값이 있는지 찾아나가는 흐름입니다.

var low = 1
var high = houses.last! - houses.first!
var maxDist = 1

while low <= high {
    let mid = (low + high)/2
    if isPossible(dist: mid) {
        maxDist = max(maxDist, mid)
        low = mid+1
    } else {
        high = mid-1
    }
}

 

그럼 이제 해당 거리를 유지해서 공유기 설치가 가능한지만 확인하면 되겠네요!

이전 집과 현재 집 사이의 거리가 원하는 거리 이상인지 체크해서

가능하다면 카운트 해주고 이전 집을 갱신해주면 됩니다. 안 된다면 설치가 불가능하니까 그냥 건너뛰어서 다음 집을 확인하면 되구요!

func isPossible(dist: Int) -> Bool {
    var count = 1
    var prev = 0
    for i in 1..<houses.count {
        if houses[i] - houses[prev] >= dist {
            count += 1
            prev = i
        }
    }
    
    return count >= nc[1]
}

 

 

해결방법

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

for _ in 0..<nc[0] {
    houses.append(Int(readLine()!)!)
}
houses.sort(by: <)

var low = 1
var high = houses.last! - houses.first!

func isPossible(dist: Int) -> Bool {
    var count = 1
    var prev = 0
    for i in 1..<houses.count {
        if houses[i] - houses[prev] >= dist {
            count += 1
            prev = i
        }
    }
    
    return count >= nc[1]
}

var maxDist = 1
while low <= high {
    let mid = (low + high)/2
    if isPossible(dist: mid) {
        maxDist = max(maxDist, mid)
        low = mid+1
    } else {
        high = mid-1
    }
}

print(maxDist)

 

배운점

이분 탐색인걸 알고 접근했는데도 너무 어려웠다... 다른 분들의 풀이를 보고도 이해가 안 가서 한참을 여러 풀이를 확인하면서 겨우 이해했다 ㅠㅠ 이렇게 지식이 +1 됐습니다..

최대한 내가 이해 못했던 부분을 중점적으로 적어봤는데 다른 분들이 이걸 보고 저처럼 고생없이 바로 이해하셨다면 좋겠다..!