[Python] 나무자르기 - 이분탐색 기본문제

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

 

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

2805번: 나무 자르기

---

2. 핵심 아이디어

이분탐색 기본 유형 중 하나

이코테 책에 있는 떡 볶이 떡 만들기 유형과 같다.

https://youtu.be/jjOmN2_lmdk

 

 

---

3. 코드

#나무자르기

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

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

start=0
end=max(k)
result=0

while(start<=end):
  mid=(start+end)//2
  temp=0
  for i in k:
    if mid<i:
      temp+=(i-mid)
  
  if temp>=m:
    result=mid
    start=mid+1
  else:
    end= mid-1

print(result)

---

4.배운점

알고 있는 문제임에도 초반 start,end 초기화를 잘못해주어 문제를 틀렸다.

이분탐색의 탐색 범위가 어느 곳인지 생각하며 초기값을 초기화해주자.