[baekjoon] 백준 2805번 : 나무 자르기 (by python 파이썬)

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

2805번: 나무 자르기

 

code

#나무 자르기
import sys
input = sys.stdin.readline

n, m = map(int,input().split())

tree = list(map(int,input().split()))

start = 1
last = max(tree)
while start <= last:
    
    mid = (start+last) //2
    count = 0
    for i in tree:
        if i > mid:
            count += (i - mid)


    if count >= m:
        start = mid+1
    
    else:
        last = mid-1

print(last)

 

이번 문제에서 어떤 방식으로 탐색해나갈지 고민을 조금 했던 것 같다.

 

처음에 바로 이분탐색을 떠올리지 못하고 고민하다 이분탐색을 생각하고는 바로 풀었다.

 

다만 처음엔 시간초과가 떴다.

 

코드의 다른점은 

count += i - mid
count = count+ (i-mid)

위 코드를 아래처럼 썼었는데 아래같은 경우에는 시간초과가 떴다.

 

아직 왜그런지 이유는 모르지만 한번 공부해야될 것 같다.

 

알고리즘 문제를 풀때 시간초과가 난다면 이런부분도 확인해 봐야겠다.