백준 2805번 나무자르기 _ 이분탐색 (python)

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

2805번: 나무 자르기

백준 2805번 나무자르기

 

이번 포스팅에서 다루게 된 2805번 나무자르기 문제는 이분탐색을 이용해야하는 전형적인 문제입니다.
N은 100만 M은 20억까지 주어질 수 있는데 시간제한이 1초라니.. 시간초과가 합리적으로 의심되지 않나요?

이분 탐색은 어떤 조건을 만족하는 것을 찾기 위해, 시작점과 끝점의 중간점을 기준으로 위 아래 탐색을 하는 방법인데요,
쉽게 말해 업다운 게임을 생각하면 된답니다!
1-100 중 79라는 숫자를 찾기 위해 79까지 찾아가는 것 보다,
처음 50 Down => 75 UP => 87 Down => 81 Down => 78 Up => 79, 총 6번만에 정답에 접근할 수 있게 된답니다.

모든 조건을 하나하나 따져보는 것이 브루트포스의 N의 시간복잡도에 비해 이분탐색은 logN의 시간복잡도가 걸리는 셈이죠!

이번 문제 역시 minvalue와 maxvalue를 구한 뒤 가운데 meanvalue로 범위를 좁혀가면서 탐색을 하였는데요.

주의할 점은!

예외 조건으로 
3 6
4 4 5
와 같이, minvalue를 리스트 중 가장 작은 값으로 잡아버리면 답을 못 찾을 수 있기 때문에 어차피 logN이라는 생각으로 그냥 minValue를 0으로 잡아주면 된답니다. 혹시 이것때문에 시간초과가 계속 나오시거나 런타임에러가 나오신 분들은 주의하세요 :)

import sys

[NUM, LENGTH] = list(map(int, sys.stdin.readline().replace("\n", "").split()))
BRANCH = list(map(int, sys.stdin.readline().replace("\n", "").split()))

sumBranch = sum(BRANCH)
maxBranch = max(BRANCH)

def findTake(minVal,maxVal):
    meanVal = int((minVal+maxVal)/2) # 자동으로 내림된다.
    cuttedBranchSum = 0
    for i in range(NUM):
        if BRANCH[i] < meanVal: cuttedBranchSum+=BRANCH[i]
        else: cuttedBranchSum+=meanVal
    if ((sumBranch - cuttedBranchSum == LENGTH)):
        return meanVal
    if ((minVal == meanVal) or (meanVal == maxVal)):
        if (sumBranch - cuttedBranchSum > LENGTH):
            return meanVal
        else:
            return findTake(minVal-1, maxVal)
    if (sumBranch - cuttedBranchSum > LENGTH):
        return findTake(meanVal, maxVal)
    else:
        return findTake(minVal, meanVal)
    
answer = findTake(0,maxBranch)
print(answer)

 

끝.