[TIL] 백준 17266 - 어두운 굴다리 ( python )

📌 문제 탐색하기

N : 굴다리의 길이

M : 가로등의 개수

x : 가로등의 위치

 

길이 N인 일직선 상에서 M개의 특정 지점이 주어집니다. 
각 지점을 중심으로 일정한 거리를 덮을 수 있는 가로등이 있습니다.

모든 구역(0 ~ N)을 덮을 수 있도록 가로등을 설치할 때, 최소한의 가로등 길이를 구하는 것이 핵심입니다.

 

1 ≤ N ≤ 100,000

1 ≤ M ≤ 100,000

1 ≤ x[i] ≤ N

가능한 시간복잡도

• 브루트 포스 ( 완전 탐색 )
  • 최악의 경우: N * M = 100,000 * 100,000 = 10^10 (시간 초과)
  • 완전 탐색은 O(N * M), 시간 초과 가능성이 매우 큽니다.
• 이진 탐색 접근
  • 최솟값과 최댓값을 기준으로 이진 탐색을 수행합니다.
  • 중간값에 대해 모든 가로등의 지점을 순회하면서 영역을 덮을 수 있는지 확인합니다.
  • 최악의 경우: O(M log N) = 100,000 * log(100,000) = 100,000 * 17 = 1.7 * 10^6
  • 이진 탐색을 사용하면 O(M log N), 해결 가능합니다.

알고리즘 선택

이진 탐색을 사용하여 중간값을 조정하며 최소 거리를 탐색합니다.

• 탐색 기준: 중간값의 거리로 모든 구역을 덮을 수 있는지 체크
• 탐색 범위: left = 0, right = N로 설정

---

📌 코드 설계하기

• 문제의 Input을 받습니다.
• left = 0, right = N 으로 설정합니다.
• 최소 조명 거리를 저장하기 위해 ans = N 으로 설정합니다.
• 이진 탐색을 실행합니다.
  • mid = (left + right) // 2
  • 모든 구역을 덮을 수 있는지 확인합니다.
    • 현재 조명(x[i])에서 mid 거리로 덮을 수 있는 최대 위치를 covered로 관리합니다.
    • covered가 N 이상이면 mid 거리로 덮을 수 있는 위치입니다.
      • ans에 mid 값을 넣어줍니다.
      • 최소 가로등 길이를 구하기 위해 mid 값을 줄여서 다시 탐색합니다. ( right = mid - 1 )
    • covered가 N 미만이면 mid 거리로 덮지 못하는 위치입니다.
      • mid 값을 키워서 다시 탐색합니다. ( left = mid + 1 )
• 최종 구해진 가로등의 길이를 출력합니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
x = list(map(int, input().split()))

left = 0
right = N
ans = N

while left <= right:
    mid = (left + right) // 2
    
    covered = 0
    possible = True
    
    for i in range(M):
        if x[i] - mid > covered:
            possble = False
            break
        covered = x[i] + mid
    
    if possible and covered >= N:
        ans = mid
        right = mid - 1
    else:
        left = mid + 1

print(ans)