[백준/2805][Python] 나무 자르기

문제

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

2805번: 나무 자르기

풀이

이진 탐색을.. 완전히 이해하고 싶었다.

간단한 문제인줄 알았는데 난관을 많이 만나버렸다..

일단, 
Test case로 
2 10
3 9
가 주어진다면 답이 0이 아니라 1이 되어야한다. 즉 처음 시작할 때 start값을 1로 세팅해주어야 한다. 

 

그리고.. 시간초과가 자꾸 나서 뭐가 문제인지 찾아보다가..

for문 사용 방식에 있어서 1번으로 하니 통과가 됐다... 2번으로 쓰신 분들 1번으로 바꿔서 해보세요

#1
  for i in tree:
    if i > mid:
      sum += i - mid
         
#2
  for i in range(len(tree)):
    if tree[i] > mid:
      sum += tree[i] - mid

코드

import sys
read = sys.stdin.readline

n,m = map(int,read().split())
tree = list(map(int,read().split()))

tree.sort()
st,end = 1,tree[-1]
result = 0
while st<=end:
  mid = (st+end)//2
  sum = 0
  for i in tree: # for i in range(len(tree)): 이렇게 하면 python통과 못함..
    if i > mid:
      sum += i - mid
  if sum < m:
    end = mid -1
  else:
    result = mid
    st = mid + 1
print(result)