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

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

2805번: 나무 자르기

클릭 시 문제 사이트로 이동합니다.

---

문제 이해

먼저 문제 이해를 하겠다. 처음에 문제를 읽으면서 무슨 말인가 했다. 절단기가 위에서 아래로 이동하는 건 줄 알았는데, 문제를 다시 읽어보니 아래 그림처럼 가로로 이동을 하는 것이었다!

문제가 요구하는 바는 위 그림처럼 나무를 잘랐을 때, 자르고 남아버린 나무조각(?)들의 높이의 합이 M보다 크거나 같음을 만족하는 H의 최솟값을 구하라는 것이다.

위 문제에서 주어지는 나무의 수는 최대 100만 개이다. 그리고 필요한 나무의 길이는 최대 20억임에 유의하자.

---

해결방법

우선 예제2를 풀이해보겠다. 주어진 M, 즉 20은 주인공이 필요로 하는 나무의 길이이다.

0부터 주어진 나무들 중에서 가장 긴 나무까지의 정수 집합에서 이분탐색을 실행한다.

예제의 입력중 가장 긴 나무의 길이는 46이다. 그러므로 46으로 설명하겠다.

{1,2,3,...,46}에서 중간인 23을 H로 두고 주어진 나무들을 잘라본다.

4-23 < 0 이므로 잘리지 않고, 26-23=3, 40-23=17, 42-23=19, 46-23=23이 나온다.

잘려나간 나무를 주인공이 모두 더했을 때 M(필요로 하는 나무의 길이) 보다 크거나 같아야 한다.

모두 더하면 0+3+17+19+23= sum = 62 >= 20(=M)이다. 다다익선이라고, 이대로 끝인 것 같지만 주어진 조건을 살펴본다.

환경에 매우 관심이 많은 상근이는 나무를 필요한 만큼만 집으로 가져가려고 한다. 그러므로 M에 최대한 근사하는 H를 찾아야한다. 그래서 이분 탐색이 필요하다.  이 문제에서는 sum이 M을 넘어서면 H를 높여서 sum을 낮추고, sum이 M보다 작으면 H를 낮춰서 sum을 높여야 한다.

4번에 수정될 사항이 있습니다.

4번에 수정될 사항이 있습니다.

집합은 41까지가 아닌 40까지이고, right = mid+1 이 아닌 mid로 해도 됩니다.

풀이

이분 탐색을 통해 해결할 수 있다.

하지만 단순히 이분 탐색만을 알아선 해결할 수 없는 테스트 케이스가 존재한다.

그래서 lowerbound의 존재를 알아야 이 문제를 풀 수 있다.

---

코드

def sol(need_length, trees):
  left = -1; right = max(trees)+1
  
  while left+1 < right:
    mid = (left+right)//2  # H의 길이

    tmp = 0  # H높이로 잘랐을 때 나오는 나무의 길이들을 모두 더한 값
    for h in trees:
      t = h - mid
      tmp += t if t>0 else 0

    if tmp == need_length: # 내가 필요한 길이랑 일치하면 그게 정답.
      return mid
    elif tmp > need_length:
      left = mid
    elif tmp < need_length:
      right = mid
  # while 탈출
  # 가장 왼쪽 반환
  # 그 이유는 왼쪽이 더 작은수, 즉 H의 최솟값.
  return left

tree_num, need_length = map(int,input().split())
trees = list(map(int,input().split()))
trees.sort()

print(sol(need_length, trees))

코드 설명

이전의 설명에 따라 코드를 짰다. 그림을 그려보며 이해하고, 따라서 코드를 짜니 수월했다.

---

 

def chk(need_length, trees):
  arr = list(range(0,max(trees)+1))
  left = -1; right = len(arr)
  while left+1 < right:
    mid = (left+right)//2
.
.
.

print(chk(need_length, trees))

메모리 초과가 난 이유는 바로 길이가 20억이나 되는 리스트를 만들었기 때문이다. 어차피 1~max(trees)의 정수 범위에서 처리하기 때문에 굳이 리스트를 만들지 않아도 충분히 풀 수 있는 문제였다.

시간 초과가 나온 이유는 left, right 범위를 제대로 설정하지 않았기 때문이다.

틀렸습니다가 나온 이유로 첫째는 upperbound로 이 문제를 해결하려 했기 때문이고, 다른 이유로는 bound 개념에 익숙지 않아 잘 모르고 mid를 출력했기 때문이다.