백준 - 공유기 설치(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2110

참고한 자료 : https://devlog-wjdrbs96.tistory.com/267

 

[문제 설명]

주어진 좌표에 공유기를 설치할 때 가장 인접한 공유기가 가장 멀게하려면 어떻게 해야할까?

[접근 방법]

접근을 못하고 아이디어도 생각 못했다.

제일 큰 문제는 내가 이걸 그래프 알고리즘으로 생각하고 아이디어를 생각한 게 가장 큰 문제다.

나는 주로 카테고리를 골라서 문제를 푸는데, 이 문제 또한 그래프로 생각하고 그래프라는 생각에 틀이 박혀 생각을 아예 못했다.

물론, 이분탐색을 워낙 안풀어서 이분탐색을 생각도 못한 게 가장 큰 문제다.

랜덤하게 아무 카테고리를 골라도 알아서 유추해서 풀 수 있어야 하는데 문제가 있어 보인다.

그래서 검색을 통해, 다른 사람 답안을 보고, 코드를 보지 않고 직접 구현해봤다.

 

접근 방법은 공유기 사이에 최대 거리부터 절반씩 잘라가면서 공유기를 놓는 것이다.

이게 사실 처음 봤을 땐 이해가 안갔다. 

사실 가장 가까운 공유기가 가장 먼 거리가 되기 위해서는 모든 공유기의 간격이 최대한 같아야 한다.

1 2 3 4 5 6 7 8 9가 있다면 1 5 9처럼 최대한 균등하게 나눠져야 되는 것이다.

따라서 최대 거리인 1~9까지의 거리인 8에서부터 시작하여, 절반씩 줄여가면서 계산하는 것이다.

 

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (N, C) = readLine().split(" ").map { it.toInt() }
    val map = IntArray(N)
    map.forEachIndexed { index, i ->
        map[index] = readLine().toInt()
    }
    map.sort()

    var left = 1
    var right = map[N-1]
    var avgDistance = 0
    while (left <= right) {
        avgDistance = left + (right-left)/2
        var installedWifi = 1

		// 새로 추가할 공유기 위치랑 거리를 비교할 위치
        var prevCity = map[0]
        for (idx in map.indices) {
            val realDistance = map[idx]- prevCity
            // 공유기가 지정한 간격보다 멀리 있으면 설치
            if (realDistance >= avgDistance) {
            	// 공유기 개수 추가
                installedWifi++
                // 이제 현재 공유기를 기준으로 거리를 재야함
                prevCity = map[idx]
            }
        }

		// C개 설치 가능하면 공유기간 간격을 늘려도 됨.
        if (installedWifi >= C) {
            left = avgDistance+1
        } else {
            right = avgDistance-1
        }
    }

    println(left-1)
}

upperBound를 사용했기 때문에 해당하는 답안 +1을 반환한다.

4가 정답이라면 5를 반환 -> -1한 값을 리턴해줘야 한다.

따라서 출력할 때 left-1을 출력해줬다.