[백준] 2805. 나무 자르기 - Python

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

2805번: 나무 자르기

---

• 생각
  • 가장 큰 나무 길이부터 1개씩 줄여가면서 원하는 나무 길이 맞추기
    • 시간 초과... 만약 자를 나무의 길이가 매우 작을 때 오래 걸릴 듯
  • 이진 탐색으로 가장 큰 나무 길이의 절반으로 잘라보고
    • 자른 나무길이가 부족하면 높이를 낮추고
    • 자른 나무길이가 남으면 높이를 올린다.
• 코드(실패-시간초과)

from sys import stdin
# 나무의 수 N, 원하는 나무 길이 M
N,M = map(int,stdin.readline().split())
tree = list(map(int,stdin.readline().split()))

# 절단기에 설정할 수 있는 최대 높이
height = max(tree)
# height로 자르면 잘리는 나무 수
cnt = 0
while M > 0 and height > 0:
    cnt += tree.count(height)
    M -= cnt
    height -= 1

print(height)

 

• 코드(성공)

from sys import stdin

# 나무의 수 N, 원하는 나무 길이 M
N,M = map(int,stdin.readline().split())
tree = list(map(int,stdin.readline().split()))

# 이진탐색
start,end = 0, max(tree)

while start <= end:
	# 자를 높이
    mid = (start + end)//2

    # 현재 자를 수 있는 나무길이
    log = 0
    for i in tree:
        if i > mid:
            log += i - mid
    
    # 원하는 나무 길이보다 작으면 높이를 down
    # 원하는 나무 길이보다 크면 높이를 up
    if log >= M:
        start = mid + 1
    else:
        end = mid - 1

print(end)