[백준] 17266: 어두운 굴다리 (파이썬, 이분 탐색)

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

▶ 구해야하는 것

N 길이의 굴다리에 M개의 가로등으로 전체 굴다리를 비춘다.

가리기 위해서는 H 높이의 가로등이 좌우로 H만큼 비추고 있다.

이 때 설치해야할 가로등의 최소 높이를 구하는 거다. 

▶ 풀이 탐색

O(M): 가로등마다 다 비출 수 있는지 확인

O(N): 가로등의 높이 탐

O(NM): 시간 복잡도가 소요됨. 약 10만^개의 연산이 필요해 시간 안에 불가능하다. -> 이분 탐색을 이용해야한다.

---

O(log N): 가로등의 높이를 이분 탐색한다.

O(M): 각 가로등마다 다 비출 수 있는지 확인한다.

총 O(MlogN)의 시간 복잡도가 소요된다.

---

1. 이분 탐색으로 가능한 최소 높이 찾기

- 규칙: 가로등의 높이가 높아지면 비출 수 있는 거리가 길어지고, 낮아지면 거리가 짧아진다.

- 가로등의 최소 높이(0)부터 최대 높이(N)까지를 이분 탐색한다.

 

2. 높이 X의 가로등이 굴다리르 모두 비출 수 있는지 확인한다.

-  가로등의 가장 왼쪽 영역: 

-  가로등의 가장 오른쪽 영역:

-  가로등의 가운데 영역: 

 

 

-> 내 알고리즘이 너무 복잡했다

▶ 코드 설계

 

▶ 정답 코드 

▶ 추가 풀이