[백준/BOJ] - 2805번 python 풀이 - 이분탐색(binary search)

---

Key Point 

1. 자르기 문제는 보통 이분탐색을 활용하면 쉽게 해결 가능하다.

2. 어떤 값으로 나무를 잘랐을 때 잘려진 나무 길이의 합이 N보다 크거나 같은 경우 낭비되는 나무의 길이를 줄이기 위해

자르는 나무의 길이 기준을 높여야 한다. -> 잘라서 나오는 나무의 길이 합이 적어짐.

3. 2의 else 상황에선 자르는 나무의 길이 기준을 낮추어야 잘라서 나오는 나무의 길이 합이 커진다.

---

정답 코드

import sys
N, M = map(int,sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))

start = 0
end = max(trees)
while start <= end:
    mid = (start + end) // 2
    total = 0
    for i in trees:
        if i > mid:
            total += i-mid
    if total < M:
        end = mid - 1
    else:
        result = mid
        start = mid + 1
print(result)

---

  시간 초과 코드

import sys
N, M = map(int,sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))
trees.sort(reverse = True)
new_total = 0
old_total = 0
old_idx = 0
total2 = 0
length = len(trees)
for i in range(1, N): #tree idx (자르는 나무)
    for j in range(i): #잘라 지는 나무 idx
        new_total += trees[j] - trees[i]
    if new_total == M:
        print(trees[i])
        break
    else:
        if (M - new_total) < 0 and (M - old_total) > 0: #new가 더크니까
            if abs(M-new_total) > abs(M - old_total):
                for k in range(trees[old_idx], trees[i]+1, -1):
                    for l in range(length):
                        if trees[l] - k > 0:
                            total2 += trees[l] - k
                        else:
                            break
                    if total2 >= M: #1cycle 돌았을 때
                        print(k)
                        exit(0)
                    total2 = 0
            else:
                for k in range(trees[i], trees[old_idx]+1):
                    for l in range(length):
                        if trees[l] - k > 0:
                            total2 += trees[l] - k
                        else:
                            break
                    if total2 >= M: #1cycle 돌았을 때
                        print(k)
                        exit(0)
                    total2 = 0

    old_total = new_total
    new_total = 0
    old_idx = i #나무 자를 길이 담겨진 idx