https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
풀이
문제가 실버라서 얕봤다가 크게 다쳤다. 조건 자체를 이해하기 어려웠는데, 가장 인접한 두 공유기 사이의 거리를 최대로 하라는 말이 와닿지 않았다. 가장 인접한, 최대 거리??
그래서 마이구미님 블로그(https://mygumi.tistory.com/301)를 참고해서 이해할 수 있었다.
위 말을 맥락적으로 해석하면, 최대한 공평하면서도 간격이 크게 공유기를 설치하라는 것이다. 특정 두 집의 사이의 설치 간격이 너무 커지면, 그만큼 나머지 설치된 집들 사이의 간격은 짧아져서 가장 인접한 설치 거리가 짧아지기 때문이다.
즉, 거리가 가장 가까운 두 공유기 사이의 거리를 k라고 하면, 나머지 인접한 공유기들 사이의 모두 k보다 크거나 같아야 한다.
ex) k = 3, 2 <-> 5 <-> 12 <-> 15 <-> 19 - (공유기가 설치된 위치)
3 7 3 4 - (사이 거리) --> 모두 3보다 크거나 같다
이 문제는 이분 탐색의 응용인 파라메트릭 서치를 통해서 해결하는 문제로 알려져 있는데, 방법은 다음과 같다.
1. 가장 인접한 공유기 사이의 거리를 대상으로 이분탐색을 진행한한다.
2. 그 거리보다 크거나 같도록하는 기준을 만족시키면서 왼쪽 집부터 공유기를 설치하면서 갯수를 센다.
3. 문제에서 주어진 공유기의 개수와 설치한 공유기의 개수를 비교해서, 같거나 더 많이 설치했다면 간격을 늘리고, 더 적게 설치했다면 간격을 줄인다.
4. left(lower) <= right(upper)일 때까지 1~3번을 반복하여 가장 인접한 설치 거리의 상한선을 찾는다.
여기서 이해가 안갔던 건 왜 왼쪽 집부터 항상 공유기를 설치하느냐는 것이었다. 정확하게 증명하려면 약간의 수학이 필요한듯 한데, 자세한 건 https://www.acmicpc.net/board/view/50802를 참고해보자.
코드
fun main(){
var n = 0
var c = 0
val listOfHouse = mutableListOf<Int>()
readLine()!!.trim().split(" ").map{ it.toInt() }.let{
n = it[0]
c = it[1]
}
repeat(n){
listOfHouse.add(readLine()!!.toInt())
}
listOfHouse.sort() // 정렬: 이분탐색의 전제 조건
var lower = 1 // 최소 간격
var upper = listOfHouse.last() - listOfHouse[0] // 최대 간격: 양 끝 집 사이의 거리
var answer = upper
while(lower <= upper){
val mid = (lower + upper) / 2
var count = 1 // 공유기 설치한 횟수
var prevHouseIdx = 0 // 직전에 설치된 집
// mid보다 인접 간격이 길거나 같도록 설치한다
for(i in 1 until n){
if (listOfHouse[i] - listOfHouse[prevHouseIdx] >= mid){
count++
prevHouseIdx = i
}
}
// c == count -> 간격을 더 늘려도 모두 설치할 수 있는지 확인해본다
// c < count -> 더 많이 설치됐다 -> 설치 간격을 늘려본다
if (c <= count){
lower = mid + 1
answer = mid
}else{ // 더 많은 공유기를 설치해야 한다 -> 간격을 줄인다
upper = mid - 1
}
}
println(answer)
}'Problem Solving > 백준' 카테고리의 다른 글
| 백준 2156번: 포도주 시식 (Kotlin) (0) | 2021.12.06 |
|---|---|
| 백준 2668번: 숫자고르기 (Kotlin) (0) | 2021.12.05 |
| (Kotlin) 백준 11057 - 오르막 수 (0) | 2021.12.01 |
| 백준 10844번: 쉬운 계단수 (Kotlin) (0) | 2021.12.01 |
| (Kotlin) 백준 9251 - LCS (0) | 2021.09.16 |