[BOJ] 2805 나무 자르기 - python

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

2805번: 나무 자르기

풀이

최적화 문제에 마주쳤는데, N이 엄청나게 크다 ⇒ 이분탐색 사용하기 → 나무의 수가 최대 1,000,000개로 매우 큼. 그냥 순차 탐색은 O(N)의 시간 복잡도를 가지지만 이분탐색은 O(log2N)의 시간복잡도를 가지기 때문에 무조건 이분탐색 써야함 기준은 '자를 높이(cut)'임. 따라서 start = 0, end = max(tree)로 설정 이분탐색을 진행하며 잘려지는 나무와 M을 비교해서 기준(mid)를 움직임 start ≤ end일때까지 이분탐색 진행

시간초과 코드

import sys
def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split(" "))
tree_height = list(map(int,input().split(" ")))

#tree - height 들의 sum >= M
#가장 max부터 1씩 줄여가며 M을 만족하는 최초의 height를 찾기

cut = max(tree_height) - 1
while(True):
    sum = 0
    for tree in tree_height:
        if tree > cut:
            sum += tree - cut

    if sum >= M:
        print(cut)
        break
    cut -= 1

코드

import sys
def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split(" "))
tree_height = list(map(int,input().split(" ")))

#tree - height 들의 sum >= M
#이분탐색 이용 #cut을 이분탐색
start = 0
end = max(tree_height)

def calculate(cut):
    sum = 0
    for tree in tree_height:
        if tree > cut:
            sum += tree - cut
    return sum

while start <= end:
    mid = (start + end) // 2
    if calculate(mid) >= M: #더 많이 잘렸으므로 cut높이를 높이기
        start = mid + 1
    else: #덜 잘렸으므로 cut높이를 낮추기
        end = mid - 1

print(end) #같은 조건에서 start를 움직이므로, 움직이지 않은 end조건을 결과로 취한다.

얻어가는 것

• 이분탐색 O(log_2N)

  #탐색할 기준을 잡고, 그것의 start, end를 설정한다.
  start = 0
  end = len(arr) -1
  
  while start <= end:
  	mid = (start + end) // 2
  	
  	#mid를 가지고 특정 값 계산, 비교
  	if function(mid) == goal:
  		print(mid)
  		break
  	else:
  		if function(mid) > goal: 
  			end = mid - 1 #왼쪽만 살림, 오른쪽 제거
  		else:
  			start = mid + 1 #오른쪽만 살림, 왼쪽 제거

• → 정렬되어 있는 리스트에서 , N이 엄청나게 큰 수 일 때, 데이터 탐색하는 방법

느낀점

"211116"

소요 시간 : 1h

• 최악의 경우 순차탐색은 O(N)만큼의 시간복잡도를 가진다는 사실을 주의하자
• 정렬 된 자료를 탐색할 때 N이 무지 크다면 이진탐색을 생각해보자