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

📌 문제 탐색하기

 양 옆으로 가로등 높이 H만큼 비추는 가로등 M개가 있다고 했을때, 길이 N의 굴다리를 전부 밝힐 수 있는 최소 가로등의 높이를 구하는 문제이다. 

🔎  시간 복잡도

• 각 가로등 간의 간격을 순회해야하므로 M+1번 비교를 해야한다. 간격을 순회하면서 해당 높이를 탐색하면 되므로,  시간 제한안에 풀 수 있다.

🔎 접근 방법 및 알고리즘

• 가로등의 높이가 클수록 더 넓은 범위를 비추고, 작을수록 적은 범위를 비춘다.
• 가로등의 높이가 가능한 범위는 0 ~ N (100,000)이다

📌 코드 설계하기

1️⃣ X의 리스트 이웃한 두 숫자 간 넓이를 순회하자.

 예를 들면 i, i + 1번째 x가 각각 3과 10이라고 한다면, 가로등의 최소 높이는  반올림한 값인 round((10 - 3) / 2)가 될 것이다. 이제 이를 맨 끝의 가로등에도 적용할 수 있는지를 보는 것이다. 

근데 이게 이진 탐색을 적용해도 되는 문제인가라는 의심이 든다. 

📌 시도 회차 수정사항

1. 테스트 케이스에 대해서만 맞혔다. 결과적으로는 틀린코드

import sys
input = sys.stdin.readline
# 입력 받기
N = int(input())
M = int(input())
x = list(map(int, input().split()))

# min은 x[0], max는 굴다리 길이 N으로 정의하기
min_len = x[0]
max_len = N

# 모든 X의 값에 대해서 탐색을 진행한다.
for i in range(0, M - 1):
    mid = round((x[i + 1] - x[i]) / 2)
    if min_len < mid:
        min_len = mid
    else:
        continue
# 위의 인덱스를 벗어나는 값에 대한 처리를 해준다. 
if (N - x[-1]) > min_len:
    res = N - x[-1]
else:
    res = min_len

print(res)

 

2. 알고리즘으로는 틀린게 없다고 생각했고 히든케이스가 있다고 생각해 가로등 수가 0개와 N개일 경우를 추가해주었다.

그래도 틀렸다.

if M == 1: res = max(x[0], N - x[0])
if M == N: res = 1

3. 세상에 알고보니 round(3.4)면 3으로 내림되는 오사오입 방법의 반올림함수였다..

이것을 수정해주니 성공했다

📌 정답 코드 

import sys
sys.stdin = open('../input.txt')
input = sys.stdin.readline

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

min_len = x[0]
max_len = N

for i in range(0, M - 1):
    if (x[i + 1] - x[i]) % 2 != 0: mid = (x[i + 1] - x[i]) // 2 + 1
    else: mid = (x[i + 1] - x[i]) // 2
    if min_len < mid:
        min_len = mid
    else:
        continue
if M == 1: res = max(x[0], N - x[0])
if M == N: res = 1

if (N - x[-1]) > min_len:
    res = N - x[-1]
else:
    res = min_len

print(res)