이진 탐색(이분 탐색): 백준 2805 파이썬

문제:

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

2805번: 나무 자르기

 

정답:

import sys

n, m = map(int, sys.stdin.readline().split())
wood = list(map(int, sys.stdin.readline().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(wood)

result = 0

# 이진 탐색 수행
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in wood:
        # 잘랐을 때 총 나무의 길이 계산
        if x > mid:
            total += x - mid
    # 나무의 길이가 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)
    if total < m:
        end = mid - 1
    # 나무의 길이가 남는 경우 덜 자르기(오른쪽 부분 탐색)
    else:
        result = mid
        start = mid + 1

print(result)

 

풀이:

이진 탐색 알고리즘을 활용해서 풀었다. total 변수에 자른 나무의 길이를 누적시키고, 그 길이가 목표 길이인 m보다 작으면 끝점의 위치를 왼쪽으로 이동하고 목표 길이 m보다 크면 시작점의 위치를 오른쪽으로 이동시킨다.

 

이 문제에서 고려해야 할 점은, if (x > mid) 이 부분이다. 각 나무의 길이 'x'보다 자르는 길이 'mid'가 더 클 경우에, 그냥

빼버리면 마이너스가 나온다. 자르는 길이가 더 크면 잘리는 나무의 길이는 '0'이기 때문에 이 상황에 대한 예외처리가 필요하다.

 

Python3로 제출하면 시간 초과가 나오지만 Pypy3로 제출하면 정답 확인을 받을 수 있었다.