[Swift 알고리즘] 백준 2110 공유기 설치

안녕하세요 코코종입니다.

오늘은 예~~전에 공부할때 못풀었던 이진탐색 문제인 공유기 문제를 가져왔습니다.

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/28.
//

import Foundation
// 2110 공유기 설치 이분탐색 골4

// idea: 공유기의 거리를 이진탐색으로 구하고 c와 같다면 답으로 인정

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0] // 집의 갯수
let c = input[1] // 공유기의 갯수
// 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치 -> 제일 붙어있는 애들끼리의 크기가 제일 크도록
// 즉, 처음에 설치를 하고 남은 갯수는 그 집들 사이에 두되 제일 붙어있는 공유기의 거리가 멀도록 한다(서로 멀게 배치한다)
// 문제 이해가 조금 어려버따...

var arr: [Int] = []
for _ in 0..<n {
    arr.append(Int(readLine()!)!)
}
arr.sort()

var answer = 0

var l = 1 // 가장 작은 거리 1
var r = arr.last! - arr.first! // 가장 긴 거리 - 처음이랑 끝 사이의 거리

func binarySearch() {
    while l <= r {
        let mid = (l + r) / 2 // 공유기와 공유기 사이의 거리
        
        var x = arr.first! // 첫 위치로 시작
        var cnt = 1 // 공유기의 갯수 - 시작점에 놓으니까 1
        
        for i in 1..<n {
            if arr[i] >= x + mid { // 다음 공유기는 현재 위치 + 공유기 거리 보다 크거나 같아야한다.
                cnt += 1
                x = arr[i] // arr[i]에 공유기 설치
            }
        }
        
        if cnt > c { // 많이 설치된 경우 -> mid 를 더 크게 가져가야함
            l = mid + 1
            answer = max(answer, mid)
        } else if cnt == c { // 알맞게 설치 된 경우 answer에 포함하되 더 큰 값이 있을 수 있어 left를 조정
            l = mid + 1
            answer = max(answer, mid)
        } else { // 너무 적게 설치된 경우
            r = mid - 1
        }
    }
    print(answer)
}

binarySearch()

또... 문제 이해가 잘 안되는 부분이 많았습니다. 제가 문제를 보고 

1. 공유기가 얼마나 넓은 범위만큼 공유가 되는건지...

2. 공유기면 양쪽에 k만큼 크기에 공유가 되는게 아닌지...

등등.. 이해가 안가는게 많았습니다. (이래서 내가 백준을 싫...어해... 공유기라고만 하면 내가 어케알아...)

문제 예시에서 '공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.' 라고 했는데 8에 설치하면 9에도 와이파이가 되는게 맞는지... 너무 불친절해효... 그래도 어떻게 합니까.. 까라면 까야지

 

사실 문제를 처음 접하면 이분탐색 문제라고 생각이 들기 어려울 것 같네요...

이분 탐색으로 1과 최대거리(arr.last! - arr.first!) 사이에서 적절한 값을 찾아냅니다.

이때 이해가 가지 않는 부분은 cnt > c 일때 answer를 포함시켜야한다는 점이었는데요... 이부분이 빠져있으면 13%에서 틀리네용 ...

제 상식상으로는 이해가 안가는 부분이었는데요 cnt가 c보다 크다면 너무 많이 설치된 경우이므로 mid를 크게 가져가기 위해

left = mid + 1로 해주는게 끝이 아닌가 싶었네요.

 

사실 완벽하게 이해하지 못했지만... 백준이 불친절해서 그렇다고 생각하겠습니다.(다른 블로그들을 몇개 봤는데도 명확하지 않네요)

나중에 생각해보니 그냥 저 집들에 공유기의 갯수를 최대한 고르게? 배분하는것 같습니다. 복습을 다시 하면 이해가 갈지도? ㅎ...

아래는 '왜 첫 집에 무조건 설치를 해야하나' 했는데 관련한 내용에 대해 검색하다가 알게된 내용입니다. 조금 오해했네요!

https://www.acmicpc.net/board/view/99986