[Python] 백준 알고리즘 2805번 : 나무 자르기

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

2805번: 나무 자르기

 

 

👩‍💻문제 이해

항상 그렇듯 이분탐색 알고리즘에서는 무엇을 변수로 둘지와 조건을 어떻게 줄지가 가장 중요하다.

(조건)

위 문제에서는 가지고 가려 하는 나무의 길이가 M으로 정해져 있기 때문에 이걸 조건으로 두면 된다.

즉, 주어진 배열 각각의 원소들을 구하고자 하는 값(target)으로 뺀 값의 합이 M이 되는 것이 조건이다.

그리고 이 때 절단기 높이의 최댓값을 구해야 하기 때문에 end값을 출력해주면 된다.

(변수)

변수가 의미하는게 뭔지 정확히 알고 있어야 한다.

우선 이 문제에서 변수는 절단기의 높이이다. 

그 다음으로 start와 end를 무엇으로 둘지 정하는 것이 이분탐색 알고리즘의 시작이다.

start는 절단기 높이의 최소값인 1로 두고, end는 배열의 최대값으로 둔다. 

 

 

 

👩‍💻반복문을 사용해 이분탐색 알고리즘 구현 (함수 별도 구현)  : 성공🌈

n,m = map(int, input().split())
li = list(map(int, input().split()))

def binary(arr, m):
  start = 1
  end = max(arr)
  
  while start <= end:
    mid = (start + end) // 2
    cnt = 0

    for i in arr:
      if i - mid > 0:
        cnt += (i - mid)   
        
    if cnt == m:
      return mid

    elif cnt <= m:
      end = mid - 1
      
    else:
      start = mid + 1
  return end
    
print(binary(li, m))