파이썬 알고리즘 309번 | [백준 2805번] 나무 자르기 - 이분탐색

309. 나무 자르기

1) 어떤 전략(알고리즘)으로 해결?

• 투포인터

2) 코딩 설명

<내 풀이>

import sys
N,M = map(int, sys.stdin.readline().rstrip().split())
trees = list(map(int, sys.stdin.readline().rstrip().split()))
trees.sort() 
l = 1
r = max(trees) 
height = 0 

while l<=r : 
    mid = (l+r)//2
    available_tree = 0
    for tree in trees : 
        if tree > mid : 
            available_tree+=tree-mid
    if available_tree >= M : 
        height = mid
        l = mid+1
    else : 
        r = mid-1

print(height) 

< 내 틀렸던 풀이, 문제점>

1. 시간초과

• 원인은 이분 탐색 left, right 증가 보폭을 잘못 설정했습니다.
• 1 씩 증가하는게 아니라 mid 를 가지고 조정하는 것이었습니다 ㅎㅎ 오랜만에 풀었더니!!

import sys
N,M = map(int, sys.stdin.readline().rstrip().split())
trees = list(map(int, sys.stdin.readline().rstrip().split()))
trees.sort() 
l = trees.index(min(trees))
r = trees.index(max(trees)) 

height = 0 

while l<r : 
    mid = (trees[l]+trees[r])/2
    available_tree = 0
    for tree in trees : 
        if tree > mid : 
            available_tree+=tree-mid
    if available_tree >= M : 
        height = mid
        l+=1
    else : 
        r-=1

print(height) 

2.

import sys
N,M = map(int, sys.stdin.readline().rstrip().split())
trees = list(map(int, sys.stdin.readline().rstrip().split()))
trees.sort() 
l = 1
r = max(trees) 
height = 0 

while l<r : 
    mid = (l+r)//2
    available_tree = 0
    for tree in trees : 
        if tree > mid : 
            available_tree+=tree-mid
    if available_tree >= M : 
        height = mid
        l = mid+1
    else : 
        r = mid-1

print(height) 

<반성 점>

• 이분탐색 템플릿을 잊었었습니다.
• mid 를 기준으로 left 와 right 을 조정해야 합니다.