[파이썬/Python] 백준 1477번: 휴게소 세우기

📌 문제 : 백준 1477번

---

📌 문제 탐색하기

N : 현재 휴게소 개수 ($0 ≤ N ≤ 50$)
M : 더 지으려는 휴게소 개수 ($1 ≤ M ≤ 100$)
L : 고속도로 길이 ($100 ≤ L ≤ 1,000, N+M < L$)
locations : 현재 휴게소 위치 ($1 ≤ locations ≤ L-1$)

문제 풀이

M개의 휴게소를 짓고 난 후 휴게소가 없는 구간의 최댓값의 최솟값을 출력하는 문제이다.

휴게소 위치들은 랜덤하게 입력되므로 탐색을 위해 먼저 오름차순 정렬해준다.

⭐️ 제약 조건

• 휴게소 세울 수 있는 위치
  • 불가능
    • 이미 휴게소 있는 곳 ❌
    • 고속도로 끝 ❌
  • 가능
    • 정수 위치
• 모든 휴게소 위치 중복 ❌

휴게소가 없는 구간의 최댓값을 조절해가면서 원하는 최소가 되는 거리를 찾으면 될 것이다.
→ 이진 탐색 활용‼️

이진 탐색 구현

• 탐색 구간 = 1부터 L-1까지 (휴게소 위치 범위에 따라)

  • start = 1
  • end = L-1
  • mid = 휴게소 없는 구간의 최댓값

• 탐색 수행

  • 해당 mid 값이 휴게소 없는 구간 중 최댓값인지 확인 필요
    • 휴게소 간 거리 계산
      • 큰 값이 있다면 그 사이에 mid만큼 떨어뜨려 휴게소 설치
      • 몇 개 설치할 수 있는지 개수 저장
  • 사이에 설치한 개수가 M과 얼마나 차이나는지 확인
    • M보다 작다 → mid 값 감소 (더 많이 세울 수 있도록)
    • M보다 크다 → mid 값 증가 (더 적게 세울 수 있도록)

• 종료 조건

  • start가 end와 같거나 더 커질 경우

가능한 시간복잡도

오름차순 정렬 → $O(N log N)$
이진탐색 → $O(N * log L)$

최종 시간복잡도
L이 N보다 크므로 $O(N log L)$가 된다.
최악의 경우 $O(50 * log(1000))$이 되어 제한 시간 2초 내에 연산이 가능하다.

알고리즘 선택

정렬 후 범위 내 이진탐색

---

📌 코드 설계하기

1. N, M, L 입력
2. 휴게소 위치 입력
3. 위치 정렬
4. 이진 탐색 구간 정의
5. 이진 탐색 구현
   5-1. 휴게소 없는 구간의 최댓값 정의
   5-2. 설치한 휴게소 수 초기화
   5-3. 휴게소 간 거리 계산해 지정한 최댓값보다 큰 값 확인
   5-4. M과 설치한 휴게소 수 비교
6. 결과 출력

---

📌 시도 회차 수정 사항

1회차

• cnt = (locations[i+1] - locations[i]) // mid로 계산한 변수에서 NameError가 발생했다.
• 개수를 세기 전에 초기화해주어야 했는데 초기화로 정의하지 않아서 발생한 문제였다.

2회차

• 예제에 대해 원하는대로 동작하지 않았다.
• 여러 오타 존재
  • 휴게소 위치에 0, L 미포함해 계산 시 누락 부분 발생
  • cnt와 M을 비교해야하는데 mid와 비교
  • 휴게소 간 거리 계산 시 범위를 N-1까지로 잘못 작성

---

📌 정답 코드

import sys

input = sys.stdin.readline

# N, M, L 입력
N, M, L = map(int, input().split())

# 휴게소 위치 입력
locations = [0] + list(map(int, input().split())) + [L]

# 위치 정렬
locations.sort()

# 이진 탐색 구간 정의
start = 1
end = L - 1

# 이진 탐색 구현
while start <= end:
    # 휴게소 없는 구간의 최댓값 정의
    mid = (start + end) // 2

    # 설치한 휴게소 수 초기화
    cnt = 0

    # 휴게소 간 거리 계산해 지정한 최댓값보다 큰 값 확인
    for i in range(len(locations)-1):
        if locations[i+1] - locations[i] > mid:
            # 휴게소 설치
            cnt += (locations[i+1] - locations[i] - 1) // mid

    # M과 설치한 휴게소 수 비교
    if cnt <= M:
        end = mid - 1
    else:
        start = mid + 1

# 결과 출력
print(start)

• 결과