인프런 커뮤니티 질문&답변

S와 E는 결국 같아지기 때문에 사실 둘 다 써도 상관 없습니다. 하지만

while s <= e : # 교차되기 전까지!
    mid = (s+e)//2

    # 얼마나 나무를 채취했나요?
    wood = 0
    for tree in forest:
        if tree >= mid:
            wood += tree - mid
    
    # 업인가요? 다운인가요?

    if wood >= M : #최소를 만족했다!
        s = mid +1
    else:
        e = mid -1
    

반복문이 종료되는 것은 S와 E가 같아진 뒤, S와 E가 교차되는 순간이기 때문에

1. 정답이 되는 높이를 찾는다

2. 조건문에 만족이 되는 "정답이 되는 높이" 이기 때문에 s = mid+1 코드가 동작하고 s와 e의 높이가 교차된다.

3. 반복문이 종료되고 e는 정답높이, s는 정답높이+1이 된다.

라서 해당 문제의 정답은 e나 s-1이 됩니다!

문제마다 e를 return하는 경우와 s를 return해야하는 경우가 나뉘는건지 좀 헷갈립니다.

이건 제가 수업하면서 이런 말씀을 드리는 게 좀 어이 없을수도 있는데 저도 이분탐색에 엄청 약해서... 매일 헷갈려 하면서 풀고 있습니다.. 이게 교육자로써 맞는 답변은 아니겠지만, 이분탐색은 잘쓰는 사람은 정말 자주 잘쓰고 안쓰는 사람은 계속 안쓰려고 하더라구요.. 익숙해져야 하는 알고리즘 중에 하나입니다 ㅠ...

안녕하세요, 민구몽 님, 인프런 AI 인턴이에요.
나무자르기 문제에서 마지막으로 e 값을 리턴해야 하는 이유는, 이분탐색 과정에서 잘라서 얻은 나무의 길이가 m보다 크거나 같을 경우에는 절단기 설정 높이를 더 높여야하기 때문입니다. 따라서 mid 값을 e로 업데이트하여 탐색을 진행하게 됩니다. 문제에서 요구하는 것이 ‘절단기에 설정할 수 있는 높이의 최댓값’이기 때문에, 최종적으로 설정할 수 있는 높이의 최댓값인 e를 출력해야 합니다.

또한, 문제마다 e 값을 리턴하거나 s 값을 리턴하는 경우는 문제에 따라 다르게 정의될 수 있습니다. 이분탐색에서 주어진 조건에 따라서 탐색 범위를 좁혀나갈 때, 종료 조건에 따라서 e 값을 리턴하는 경우도 있고, s 값을 리턴하는 경우도 있습니다. 따라서 문제를 해결하는 과정에서 어떤 값을 리턴해야 하는지 문제의 조건과 내용을 잘 이해하여 판단해야 합니다.

이해에 도움이 되셨기를 바라며, 추가로 궁금한 점이 있다면 언제든지 질문해주세요. 감사합니다!