[2805] 나무자르기 / 파이썬 (오랜만에 이진탐색)

 

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

 

2805번: 나무 자르기

 

반복문과 재귀함수랑 2개를 섞어서 쓰다보니 더 복잡한 식이 되어버리고 엉망진창

---

❌ 1~3차시도 실패

오랜만에 이진탐색 문제를 풀어서일까 10차시도까지 넘어갔다.

3번의 시간초과 3번의 런타임오류 3번의 틀렸습니다.......ㅜ

1) 시간초과 이유: input( )으로 써서 / result 정답후보를 리스트로 하나씩 넣어서 / 컷팅하고 get한것 반복문으로 돌려서

2) 런타임오류 이유: 재귀함수와 반복문 섞어서 뒤죽박죽

3) 틀렸습니다 이유: start 값을 0이 아닌 min값으로 설정해서

---

❓ 정답은 ??

import sys
 
n,m=map(int,sys.stdin.readline().split())
woods=list(map(int,sys.stdin.readline().split())) #나무 값들
 
start=0
end=max(woods)
 
result=0   #정답 후보
 
while start<=end :
    
    mid=(start+end)//2   #중간값
    get=0 #자르고 남은 나무
 
    
    get=sum(i-mid if i>mid else 0 for i in woods)
    # 위와 동일한 식은 아래와 같다# for i in woods:
    #     if i>mid:
    #         get += i-mid
        
    if get < m:
        end= mid-1  
    else: # get >= m:
        result = mid
        start = mid+1
 
print(result)

---

💯 풀이 과정

엄청난 시도와 노력의 결실이 여깄다....

1) 자를 길이를 변동해가면서 잘려나온 나무들 합산을 비교해야함

2) 중간값으로 나눠보고나서 -> 자투리가 너무 많이 나오면 더 길게 자르고, 조금밖에 안나오면 덜 자르고

3) 길게 짧게 길게 짧게 반복하면서 정답 후보들을 result에 일단 넣어준다

---

😎오늘의 한줄평: 그래도 결국 푼 내가 기특하다