[백준/Python] 17266 어두운 굴다리

 

📌 문제 탐색하기

• 길이 N(1 ≤ N ≤ 100,000)의 굴다리가 있음
• 굴다리에 높이가 같은 가로등 M(1 ≤ M ≤ N)개를 위치 x들에 각각 설치
• 각 가로등은 정해진 높이만큼([x-H ~ x+H]만큼) 주위를 비출 수 있음
• 굴다리의 모든 길을 밝힐 수 있는 가로등의 최소 높이 구하기

단순 완전탐색으로 최소 높이를 찾을 경우, 굴다리의 길이가 N이고, 각 굴다리 높이(총 M개)에 대해 모든 길을 비출 수 있는지 확인해야하므로, O(N*M)의 시간이 소요될 수 있다.

 

시간 내에 문제를 해결하기 위해, 이분 탐색 알고리즘을 사용할 수 있다. 가로등 높이의 범위가 1부터 N이므로, 이 범위 내에서 이분 탐색을 진행하면, O(logN)으로, 총 탐색 시간복잡도가 O(M*logN)가 된다.

 

---

📌 코드 설계하기

1. 굴다리의 길이 N을 입력받는다.
2. 가로등의 개수 M을 입력받는다.
3. 가로등의 위치 positions를 리스트로 입력받는다.
4. 가로등 사이의 간격을 계산해 distances 리스트에 저장한다.
   • 이때, 0부터 첫번째 가로등까지, 마지막 가로등부터 N까지의 거리도 계산
   • 가로등 사이의 간격은 양쪽 가로등에서 비출 수 있으므로 2를 나눠준다.
5. 이분 탐색을 수행하기 위해, low를 1, high를 M으로 설정하고 mid를 구해서 탐색을 시작한다.
6. 현재 가로등 높이로, 굴다리 전체를 밝힐 수 있는지 확인한다.
   1. 만약 현재 높이로 굴다리를 밝힐 수 있다면, 더 작은 높이로 가능한지 확인하기 위해 high를 mid-1로 줄인다.
   2. 만약 밝힐 수 없다면, 더 큰 높이여야하므로 low를 mid + 1로 증가시킨다.
7. 5번 과정을 반복하여 low, high가 교차하는 순간, 최소 높이가 되고 해당 값을 출력한다.

---

📌 정답 코드

import math

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

distances = [positions[0]]
for i in range(M-1):
  distances.append(math.ceil((positions[i+1]-positions[i])/2))
distances.append(N-positions[M-1])

low = 1
high = N

def can_iluminate(H):
  for distance in distances:
    if distance > H:
      return False
  return True

while low <= high:
  mid = (low+high)//2  
  if can_iluminate(mid):
    high = mid - 1
  else:
    low = mid + 1
print(low)

 

위의 방법으로 정답을 받긴 했지만, 가로등 사이의 간격이 클수록 필요한 높이가 더 커지는 것이므로, 결국 가로등 사이 간격 중 최대값을 찾으면 그게 정답이 되는 것이 아닌가?라는 생각이 들었다. 그래서 아래와 같이 이분탐색을 사용하지 않고 기존에 만들어둔 가로등 간격을 저장한 distances 리스트를 활용해서 코드를 고쳤고, 이 코드 역시 정답을 받을 수 있었다.

import math

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

distances = [positions[0]]
for i in range(M-1):
  distances.append(math.ceil((positions[i+1] - positions[i])/2))
distances.append(N-positions[M-1])

# 가로등 사이 간격 중 가장 큰 값 출력
print(max(distances))