[백준/Kotlin] 휴게소 세우기(1477)

🔗 문제 링크

백준 - 이분 탐색 | 휴게소 세우기(1477)

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

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

---

✔️ 소요된 시간

40분

---

✨ 수도 코드

처음에 문제를 봤을 때는 단순하게 각 휴게소 사이의 거리를 기준으로 내림차순 정렬하고, 거리가 가장 큰 값부터 그 중간에 새로운 휴게소를 설치하면 되지 않을까? 생각했습니다. 그래서 이게 왜 이분탐색 문제인지 의문이 들었는데, 이 방법대로 구현할 경우 문제가 있었습니다

 

위 그림에서 보면 노란색이 기존의 휴게소 위치라고 했을 때, 각각 4, 6, 8, 2의 거리만큼 떨어져있습니다. 처음 생각대로 구현한다면 길이 8인 구간의 가운데에 새로운 휴게소를 설치하고, 다음으로 6인 구간, 4인 구간 순으로 가운데에 휴게소를 배치하게 됩니다. 이 경우 최종적으로 최대 구간의 길이는 4가 됩니다.

하지만 위 그림처럼 배치한다면 최대 구간의 길이를 3으로 만들 수 있습니다. 구간의 가운데에 휴게소를 놓는 것이 가장 최적화된 방법이 아니라, 여러 개를 배치할 수 있다는 것이 첫번째 방법의 문제점이었습니다.

 

그래서 고민해본 결과, 최대길이를 특정 값으로 지정했을 때 배치 가능한 휴게소의 수를 세면서 최대 길이의 최소를 찾아나가는 방법을 생각했습니다.

 

예를 들어 위 그림에서 최대 길이를 4로 만들기 위해서는 2개를 배치해야 하고, 3으로 만들려면 3개, 2로 만들려면 5개가 필요하다는 것을 구해냅니다. 이때 K가 3이기 때문에 3개를 사용하면서 최소의 길이가 되는 3이 정답이 되게 됩니다.

 

🔥 최종 코드

// 3차시 2024.07.24.수 : 백준 - 휴게소 세우기(1477)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main() {
  // ✅ Input
  val br = BufferedReader(InputStreamReader(System.`in`))
  var st = StringTokenizer(br.readLine())

  val N = st.nextToken().toInt() // 현재 휴게소의 개수
  var M = st.nextToken().toInt() // 더 지으려고 하는 휴게소의 개수
  val L = st.nextToken().toInt() // 고속도로의 길이

  val position = mutableListOf<Int>() // 휴게소의 위치
  position.add(0)  // 시작 위치
  position.add(L)  // 끝 위치
  st = StringTokenizer(br.readLine())
  for(i: Int in 1..N) {
    position.add(st.nextToken().toInt())
  }

  // ✅ Solve
  position.sort() // 오름차순 정렬

  var left = 1 // 0으로 하면 런타임 에러 (/ by zero) 발생
  var right = L
  while(left <= right) {
    var mid: Int = (left + right) / 2 // 최대 길이

    var cnt = 0
    // 최대 mid 길이만큼씩 떨어지게 휴게소 배치했을 때, 필요한 새 휴게소의 개수
    for(i: Int in 1..position.size - 1) {
      cnt += (position[i] - position[i - 1] - 1) / mid
      // 1을 빼주는 이유: i번 휴게소와 i-1번 휴게소 사이의 거리가 mid의 배수라면 새 휴게소가 하나 덜 필요함
    }

    // 필요한 휴게소의 개수가 M개 이상이라면, 최대 길이를 늘려야 함
    if(cnt > M) left = mid + 1
    // M개 이하라면, 더 짧은 길이를 최대로 해도 가능한지 체크하기 위해 최대 길이 줄이기
    else right = mid - 1
  }

  // ✅ Output
  print(left)
}

---

📚 새롭게 알게된 내용

알고리즘 분류가 이분 탐색이라는 걸 알지 못했다면 풀이 방법을 생각해내는 게 더 어려웠을 것 같습니다...! 이분 탐색이라고 생각되지 않는 문제들도 한 번쯤 이분 탐색으로 풀어낼 수 있는 방법을 고민해보면 좋을 것 같다는 생각을 했습니다

 

 

3-jung0115 by jung0115 · Pull Request #129 · AlgoLeadMe/AlgoLeadMe-4