BOJ_2805 : 나무 자르기

👉 문제링크

2805번: 나무 자르기

---

---

🔸 문제 분석 🔸

• 나무의 수, 원하는 목재 길이, 나무들의 크기가 주어진다.
• 어느 높이의 절단기로 잘랐을때 최대 높이로 충분한 목재를 확보할 수 있는지 구한다.

🔸 코드 🔸

# python3 : 39% , pypy : 통과
import sys
input = sys.stdin.readline

N, M = map(int,input().split())
arr = list(map(int,input().split()))
left, right = 1, max(arr)

while left <= right:
    mid = (left+right) // 2

    tree = 0
    for i in arr:
        if i > mid:
            tree += i - mid
    
    if tree >= M:
        left = mid + 1
    else:
        right = mid - 1
print(right)

🔸 코드 해석 🔸

• 절단기의 높이를 이분탐색으로 구한다.

 

🔸 오답 코드 🔸

# python3 :47% , pypy : 47%

import sys
input = sys.stdin.readline

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

arr.sort()

answer = arr[-1]
tree = 0

while tree < M: # 절단기의 높이(answer) 하나씩 낮추기
    left = 0
    right = N-1
    answer -= 1
    
    while right > left: # 잘리는 나무중에 가장 작은 인덱스 찾기
        mid = (left+right)//2
        if arr[mid] <= answer:
            left = mid+1
        else:
            right = mid
    tree += N - right
print(answer)

🔸 코드 해석 🔸

• 잘리는 나무중에 가장 작은 인덱스를 이분탐색으로 찾는다.
• 절단기 높이를 1씩낮추며 잘리는 나무의 양을 합한다.

---

🔸 다른 코드 🔸

🔸 코드 해석 🔸

• pypy가아닌 python3로 풀이한 코드이다.
• 정확하진 않지만 Counter 클래스를 이용해 조건(절단기보다 높은)에 맞는 나무들의 합으로 판별하고, 이분탐색을 진행하는 것 같다. 
• 출처 : https://www.acmicpc.net/source/30566317

---

🔸 end 🔸

• 생각보다 어려웠다. 이분탐색을 사용해야하는 문제여서 많은 시간초과에 시달렸다.
• 이분탐색을 적용해야하는 부분도 많이 헷깔려서 푸는 시간도 오래걸렸다.
• 원래 풀었던 나무 인덱스를 이분탐색으로 찾는 코드는 python3, pypy둘다 시간초과가 나서,
  절단기 높이를 이분탐색으로 찾는 코드로 바꿔서 돌렸더니 pypy만 성공했다.
• python3로 통과한 분들 코드를 보니 collections 모듈의 Counter 클래스를 사용했다.
  해석이 완벽하진 않지만 조금 이해가 되기도 했다. (직접 구현할 염두는 안났다)
• 이 문제는 이분탐색 말고도 매개변수탐색 문제인데, 조건을 만족하는 최대값을 찾는 것이라고 한다. (출처)
• 내일이면 solved.ac의 class 2 의 모든문제를 풀게된다. 이번 문제처럼 푸는데 오래 걸리는 문제들이 많아질텐데, 짧게 풀고 넘기려하지말고 딱 1시간 집중해서 풀도록 노력해야겠다.