백준 - 2805. 나무자르기 파이썬

2805번: 나무 자르기

1. SOLUTION

이분탐색(이진탐색) 기본문제! 아무생각없이 풀면 시간초과 난다....

알고리즘 1도 모르고 풀다가 무수한 시간초과와 싸웠던 과거의 나🤦‍♀️

ㅎ......꼭 이분탐색이 무엇인지, 코드는 어떤 식으로 짜는지 학습한 후에 푸는 것을 추천한다.

 

• 나무 길이의 최소값인 1을 first로, 나무 길이 중 가장 긴 것을 last로 두고,
• first가 last보다 커지기 전까지 while문을 돌린다.
• 두 값의 중간값을 벌목높이(h)로 설정, 상근이가 가져가려는 나무(cnt)가 목표치(m)보다
  • 크면 : h+1을 first로 두고 재탐색
  • 작으면 : h-1을 last로 두고 재탐색 

 

2. CODE

n, m = map(int, input().split())
trees = list(map(int, input().split()))
first, last = 0, max(trees)

while first <= last:             # first가 last보다 작거나 같을 동안만 반복
    h = (first + last) // 2      # 중간값
    cnt = 0                      # 상근이가 가져간 나무
    for i in trees:              # trees를 돌면서
        if i > h:                # i(나무 높이)가 h보다 크면
            cnt += i - h         # 자른다! cnt에 더해주기
    if cnt >= m:                 # 가져간 나무가 목표치 m보다 크면
        first = h + 1            # first를 h보다 1 높게 설정
    else:                        # m보다 작거나 같으면
        last = h - 1             # last를 h보다 1 작게 설정
# first가 last보다 커지는 순간 반복 종료
print(last)