[파이썬/Python] 백준 17266번: 어두운 굴다리

숨·2024년 9월 21일

코테

알고리즘 문제 풀이

목록 보기

81/105

📌 문제 : 백준 17266번

📌 문제 탐색하기

N : 굴다리 길이 $(1 ≤ N ≤ 100,000)$
M : 가로등 개수 $(1 ≤ M ≤ N)$
x : 가로등 위치 $(0 ≤ x ≤ N)$

굴다리 길이 N에 M개의 가로등을 세울 때 굴다리를 모두 비출 수 있는 가로등의 최소 높이를 찾는 문제이다.

문제 풀이

⭐️ 가로등 설치 조건

가로등 개수 M개, 각 가로등 위치 x로 이미 정해진 상태

위치 x는 오름차순으로 입력, 중복 ❌, 정수

🚨 가로등 높이 조건

가로등 높을수록 비쌈

모든 가로등 높이 동일 & 정수

가로등 높이 H라면 왼쪽 H & 오른쪽 H 밝힘

굴다리를 밝힐 수 있는 가로등의 최소 높이를 구해야 한다.
→ 가로등 높이가 될 수 있는 범위 내에서 적절한 최소 높이를 이분탐색으로 찾는다.

가로등 높이는 최소 1부터 가로등 하나로 모든 굴다리를 밝힐 수 있는 높이 N까지 가능하다.

1 ~ N 사이를 중앙값부터 굴다리 길이 모두 밝힐 수 있는지 확인한다.

불가능 → 높이를 더 늘려본다
가능 → 최소 찾기 위해 높이를 더 줄여본다

확인 방식은 위치를 하나씩 접근하면서 각 위치 간 거리가 해당 가로등 높이로 커버가 되는지 확인한다.
모든 길이를 밝힐 수 있는지에 대한 결과로 이분탐색을 수행해야 한다.
→ 확인 과정에 대한 코드는 함수로 따로 만든다.

👌 확인 과정

첫번째 가로등 : 가로등 위치가 가로등 높이보다 커야함

두번째 ~ M-1 가로등 : 사이 간격이 가로등 높이의 2배보다 커야함

마지막 가로등 : 굴다리 끝에서 가로등 위치까지 거리가 높이보다 커야 함

→ 위의 조건을 모두 통과하면 가능한 가로등 높이!!

가능한 시간복잡도

1 ~ N 사이 이분탐색 → $O(log N)$
모든 굴다리 밝힐 수 있는지 확인하는 함수 → $O(M)$

최종 시간복잡도
$O(M * log N)$ 으로 최악의 경우 $O(100,000 * log(100,000)) = O(1,660,964)$ 가 되는데 이는 1초 내에 연산 가능하다.

알고리즘 선택

1 ~ N 사이 이분탐색해 얻은 높이로 모든 가로등이 길을 밝히는지 확인하기

📌 코드 설계하기

모든 굴다리 밝힐 수 있는지 확인하는 함수 정의
필요한 입력 받기
정답 저장할 변수 초기화
이분탐색 변수 정의
이분탐색 수행 (+ 확인 함수 수행)
결과 출력

📌 시도 회차 수정 사항

1회차

    x = list(map(int, input()))
        ^^^^^^^^^^^^^^^^^^^^^^^
ValueError: invalid literal for int() with base 10: ' '

공백 기준 분리해서 리스트로 입력받으려고 했는데 또 split()를 빼먹었다.

📌 정답 코드

import sys

input = sys.stdin.readline


# 모든 굴다리 밝힐 수 있는지 확인하는 함수
def is_possible(location, height):
    # 첫번째 가로등
    if height - location[0] < 0:
        return False
    # 사이 가로등
    for i in range(1, M):
        if location[i] - location[i-1] > 2 * height:
            return False
    # 마지막 가로등
    if N - location[-1] > height:
        return False
    # 모든 조건 통과하면 모두 밝힌 것
    return True


# N 입력
N = int(input())

# M 입력
M = int(input())

# 가로등 위치 입력
x = list(map(int, input().split()))

# 이분탐색 시작, 끝 정의
start = 1
end = N

# 정답 높이 정의
answer = N

# 이분탐색 실행
while start <= end:
    # 중앙값 정의
    mid = (start + end) // 2

    # 모두 밝히는 것 가능하면 높이 줄여보기
    if is_possible(x, mid):
        answer = mid
        end = mid - 1

    # 불가능하면 높이 늘리기
    else:
        start = mid + 1

# 결과 출력
print(answer)