[항해99] 99클럽 코테 스터디 6일차 TIL + 이분탐색(백준 2805 나무 자르기)

99클럽 코테 스터디 6일차 TIL + 이분탐색(백준 2805 나무 자르기)

1. 오늘의 학습 키워드

• 이분탐색
• 백준 2805 나무자르기

2. 공부한 내용

2. 1. 이분 탐색을 활용해 높이 찾기

• 절단기 높이를 이진 탐색으로 찾아가는 방식
• 이분탐색의 기본적인 틀을 기억했다면 쉽게 풀이할 수 있음
• left, right, mid 변수 활용

left = 0
right = 10**9

while left <= right:
    mid = (left + right) // 2
    # 조건 확인 후 범위 조정
    if result >= M:
        answer = mid  # 가능한 값 저장
        left = mid + 1  # 더 큰 값 확인
    else:
        right = mid - 1  # 더 작은 값 확인

2.2 나무 자르기 로직 구현

• 각 나무별 잘린 길이 계산 방법
• 누적 합 계산 및 조기 종료 조건 처리
• 불필요한 방법 방지를 위한 break 활용

2.3 정답 코드

# 항해99 6일차
# 백준 2805번 나무 자르기

import sys  
input = sys.stdin.readline

N, M = map(int, input().split()) # 나무의 수, 집에 가져가려는 나무의 길이  
tree = list(map(int, input().split())) # 각 나무의 높이

answer = 0 # 최종 답  
left = 0  
right = 10\*\*9

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

for i in tree:
    if i > mid:
        result += i - mid

        if result > M: # result가 M보다 크면 더 이상 계산할 필요 없음
            break


if result >= M: # result가 M보다 크거나 같으면 더 높이를 올려야 함
    answer = mid
    left = mid + 1 
else: # result가 M보다 작으면 더 낮춰야 함
    right = mid - 1


print(answer)

3. 오늘의 회고

• 두 가지 테스트 케이스에 대해서 동일한 답이 나왔는데 제출하면 틀렸다고 나왔다. 도무지 뭐가 문제인지 모르겠어서 GPT한테 물어봤더니, left = 1로 설정했었어서 문제가 발생했었다. 이런 사소한 처리가 문제를 틀리게 한다는 점 기억해야 한다.