[이코테]떡볶이 떡 만들기 / [백준]2805번: 나무 자르기

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

2805번: 나무 자르기

---

둘이 같은 문제임

 

처음에는 단순하게 배열을 정렬을 하고,

높이를 배열요소의 최댓값으로부터 1씩 줄여나가며 매번 잘린 나무의 길이를 계산, 비교해나가는 방식을 생각했다

 

근데 이건 너무 무식한 방법이기도 하고 무엇보다 시간이 엄청 오래 걸릴 것 같았음

---

그래서 이진탐색으로 풀었다.

이진탐색으로 풀면 탐색범위를 절반씩 줄여가며 풀 수 있으니 연산 수행 시간이 눈에 띄게 줄어들 것이다.

 

일단 내 아이디어는 이랬음

 -배열을 정렬한다

 -시작점은 0, 끝점은 배열의 마지막값(가장 큰 값)으로 설정하고 이진탐색 수행

 -나무 길이가 남는다면 시작점 = (중간점+1)로 설정하고 다시 이진탐색 수행

 -나무 길이가 부족하다면 ...

 

멍청이었던 나는 여기서 갑자기 말도안되는 생각을 해버리고 마는데..

 

 나무 길이가 부족할 경우, mid가 start가 될 때까지 mid값을 1씩 감소시킨다.

 감소시키다가, 잘린 나무 길이가 원하는 값보다 크거나 같아지는 시점의 mid값을 리턴한다.

 

 

......?????? ^^ ???

 

---

물론 이렇게 한다고 답이 안 나오는 건 아니다

근데 이건 이진탐색이 아니고 사실상 선형탐색이나 다름없다

최악의 경우(최소높이가 최초 중간점보다 아래 형성되는 경우)에는 선형탐색 하는 거랑 시간복잡도가 동일할 것임.

#절단기 높이가 height일 때 잘린 나무의 길이 리턴하는 함수
def cut(arr, height):
  sum = 0
  for i in arr:
    if i>=height:
      sum += i - height
  return sum


def search(arr, target, start, end):
  while start <= end:
    mid = (start+end)//2
    #길이가 남으면, start 위치 조정.
    if cut(arr,mid) > target:
      start = mid + 1
    #길이가 부족하면.....^v^
    else:
      while mid >= start:
        if cut(arr,mid) >= target:
          return mid
        mid -= 1
  return None
  
n,m = map(int,input().split())
arr = list(map(int,input().split()))

arr.sort()

print(search(arr, m, 0, arr[n-1]))

이게 내가 처음에 짠 말도안되는 코드고 , 결과는 당연히 시간초과였다

 

---

제대로 풀어보기

 

 -배열을 정렬한다 (굳이 필요없음)

 -시작점은 0, 끝점은 배열의 마지막값(가장 큰 값)으로 설정하고 이진탐색 수행

 -나무 길이가 남는다면 시작점 = (중간점+1)로 설정하고 높이를 저장 후 다시 이진탐색 수행

 -나무 길이가 부족하다면 높이를 저장하지 않고 끝점 = (중간점-1)로 설정하고 다시 이진탐색 수행

 -이진탐색이 종료되었을 시점에서 저장되어있는 높이를 리턴

---

이제 알았으니 다시 코드를 수정해보도록 하자..

#절단기 높이가 height일 때 잘린 나무의 길이 리턴하는 함수
def cut(arr, height):
  sum = 0
  for i in arr:
    if i>=height:
      sum += i - height
  return sum


def search(arr, target, start, end):
  result = 0
  while start <= end:
    mid = (start+end)//2
    #길이가 남으면, start 위치 조정하고 높이 저장
    if cut(arr,mid) >= target:
      result = mid
      start = mid + 1
    #길이가 부족하면, end 위치 조정
    else:
      end = mid - 1
  return result
  
n,m = map(int,input().split())
arr = list(map(int,input().split()))

print(search(arr, m, 0, max(arr)))