2805번: 나무 자르기 (acmicpc.net) 문제 질문

[kugorang]

@10kseok 님 질문

---

2805번: 나무 자르기 (acmicpc.net) 문제에서, 이진 탐색으로 푸는 경우. 아래와 같이 상한(upper) 값을 반환하여야 정답으로 확인했습니다.

while lower <= upper:
    ...
    cutting_height = (lower + upper) // 2
    ...

    if total_tree >= M:
        # 필요량 초과시 절단 높이 증가
        lower = cutting_height + 1
    elif total_tree < M:
        # 필요량 부족시 절단 높이 감소
        upper = cutting_height - 1

print(upper)

하지만 상한(upper) 값은 while문을 벗어났을 때, lower 보다 작기 때문에 문제에서 원하는 최대 벌목 높이에 맞지 않다고 생각했습니다.
제가 생각하기에, 모아야 하는 나무(M)보다 “크거나” 같은 값을 자르기 위해 이러한 결과가 나오는 것 같은데, 혹시 이에 해당하는 케이스를 알고 계신 분이나. 다른 의견이 있으신 분 있으시나면 조언 부탁드리겠습니다…!

[kugorang]

@10kseok 님 답변

---

그것은 제가 답변해 드리겠습니다.
우선, 하한선은 필요양을 충족시키거나 넘기는 벌목 높이입니다.
while문을 빠져나온 상황을 보면,
하한선이 상한선보다 높은 경우입니다.
이 때 사실 절단 높이(cutting_height)도 하한선과 같은데요.
여기서 하한선 - 1 값은 무조건 필요량을 충족시키거나 넘기는 값이 됩니다. 왜냐하면 하한선이 설정될 때 필요량을 초과하면 + 1이 되는 구조이기 때문이죠.
그래서 이 상한선은 while문을 벗어났을 때 하한선 - 1 인 형태가 되는데, 이는 필요양과 같거나 클 수 있는 경우에서 가장 높은 높이가 됩니다. 따라서 출력값으로 upper 또는 lower - 1을 출력할 수 있습니다.
감사합니다.