[백준/Swift] 2110 공유기 설치

안녕하세요!

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

2110번: 공유기 설치

---

• 문제부터 파악하겠습니다.

좌표 0~ 1,000,000,000 이내의 수직선에

집 N개기 있습니다.

이 집에서 공유기를 설치하려고하는데 < 한 집에는 1 개의 공유기> 만 설치가 가능합니다.

 

이때 구해야 할 것은 가장 인접한 두 공유기 사이의 거리가 가능한 크게!!! 설치를 하는것입니다.

---

 

 

좌표 상의 집이 엄청 많이 있을 수 있는데, 그 집들을 고려하는게 아니라, 공유기를 설치했을 때, 공유기와 공유기를 중심으로 문제를 풀어야 합니다. 가장 인접된 두 공유기 사이의 거리가 긴 거리를 구하는게 문제의 핵심입니다.

....

 

• 핵심 포인트 1

input

3 2

1

3 

10

이라고 할 때

 

공유기 2개가 설치가 된다면 . "집과 집"이 중심이 아니고

"집에 설치된 공유기"와 공유기를 중심으로만 바라볼 때 그 둘 간 거리가 "최대한 큰 값이 되도록"하는 방법은?!

 

첫번째 집에 무조건 설치를 하는 것입니다.

따라서 1 과 10 좌표에 설치했을 때 가장 큰 값을 얻을 수 있습니다.

---

이 경우에도 

집이 있는 좌표가 1,2,3,5,8,9,10,11 일 때 

공유기 간 거리가 최대한 큰 값이 되도록 하는 방법은?

좌표가 2를 기준으로 두는게 좋을까요? 5를 기준으로 두는게 좋을까요?

2에 공유기를 설치했을 때 공유기간 거리가 가장 큰 값이 되도록 하는 집의 위치는 11이 될 것이고

위치가 5에 공유기를 설치했다면 공유기간 거리의 최대는 6이 됩니다.

 

하지만 1 과 11에 공유기를 설치했을 때 10이라는 가장 큰 거리를 얻을 수 있습니다.

 

...

 

따라서 공유기를 설치할 때

가장 왼쪽에 있는 집에 먼저 1개를 설치한 다음에,

추가로 공유기를 어디에 설치할지 고민하는게 "공유기 간 거리가 최대한 큰 값"에 가까워집니다.

 

---

 

• 핵심 포인트 2

이분탐색을 수행할 때는 반드시 mid의 조건을 지정해야 합니다.

집의 맨 왼쪽을 left, 오른쪽을 right로 둘 경우

 

mid는 (가장 인접한) 두 공유기 사이의 거리로 정할 수 있습니다.

핵심 포인트 1 과 같이 첫번째 집에 공유기를 선택하는 것이 바람직한 첫 공유기 설치 과정임을 알았음으로 

첫번째 집을 기준으로 우리가 정한 mid 거리만큼, 거리보다 크거나 같은 위치의 집에 두번째 공유기를 설치할 수 있습니다.

이제 두번째 공유기를 기준으로 mid거리만큼, 거리보다 크거나 같은 위치의 집에 세번째 공유기를 설치할 수 있습니다 의 반복을 통해 공유기를 "우리가 지정한 인접한 두 공유기 사이의 거리"에 따라 설치할 수 있습니다.

 

이때 mid 값은 그냥 인접한 두 공유기 사이의 거리를 정한 것이므로

문제에서 정의된 공유기의 개수만큼 공유기를 설치할 수도, 설치하지 못할 수도 있습니다.

 

""" 

      지정된 개수만큼 공유기 설치 조건을 만족하는가?

      수직선상의 집에서 첫번째 집과 거리가 mid 이거나 그 이상인 집에 공유기를 설치합니다.

      최근에 공유기를 설치한 집을 기준으로 거리가 mid 이거나 그 이상인 집에 공유기를 설치합니다.

"""

의 반복을 Xn까지 한 후에 설치된 공유기 개수를 얻을 수 있습니다.

이때 우리가 설치했던 공유기 개수가 문제에서 제시된 공유기 설치 수 보다 작다면!

공유기 사이의 거리를 크게 측정했기 때문에 공유기와 공유기 사이의 간격이 큰 것이므로, 공유기 사이의 거리를 줄이도록 mid를 설정한 후에 다시 위의 지정된 개수만큼 공유기 설치조건을 만족하는지 측정해나갑니다.

 

이때 주의해야 할 점이 특정 mid가 지정된 개수만큼 공유기의 설치 조건을 만족했을 때, 

문제에서 구해야 하는 것이 가장 인접한 두 공유기 사이의 거리가 "가능한 큰 값"이므로 mid의 오른쪽을 탐색 하면서 만약 지정된 개수만큼 공유기 설치 조건을 만족 값이 나오면 그 값을 result로 갱신해야합니다.

---

다음은 제 코드입니다.

import Foundation

// 이때의 mid는 가장 인접한 두 집 사이의 공유기 거리 입니다.
func binary_search(house : [Int], installRouter C : Int) -> Int{
    var answer = 1
    var left   = 1
    var right  = 1000000000
    
    while(left <= right){
        let mid = (left + right) / 2
        if isInstall(width: mid,installRouter: C,house: house) {
            //주의 해야 할 곳
            if mid > answer{
                answer = mid
            }
            left  = mid + 1
        }else{
            right = mid - 1
        }
    }
    return answer
}

func isInstall(width w: Int,installRouter C : Int,house h : [Int]) -> Bool{
    var install      = 1
    var installCoord = h[0]
    for x in 1..<h.count{
        if h[x] - installCoord  >= w{
            installCoord = h[x]
            install += 1
        }
    }
    
    if install >= C {return true}
    else {return false}
}

func BOJ_2110(){
    var NC    = readLine()!.split(separator: " ").map{Int(String($0))!}
    var N     = NC[0]
    var C     = NC[1]
    var house = [Int]()
    
    for i in 0..<N{
        house.append(Int(readLine()!)!)
    }
    house.sort(by: <)
    var answer = binary_search(house: house, installRouter: C)
    print(answer)
}

BOJ_2110()

긴 글 읽어주셔서 감사합니다.