백준 2805 문제 링크

💡 1. 문제 정의

이 문제는 이진 탐색 기법을 활용하여 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제이다.
시간초과를 잘 고려해서 풀어주어야 해결이 되는 문제였다.

🤔 2. 해결 방법

이진 탐색을 활용하여 절단기의 높이를 시작점, 중간점, 끝점을 이용해 가장 최적의 절단기의 높이를 구해준다.

📑 3. 문제 풀이

• 계속해서 실패했던 이유가 바로 시간초과였다.
• 실패했던 요인은 바로 2가지였다.
  1. 입력을 input() 함수로 받았다.
  2. while문 안의 for문에서 조건문을 "if (t - mid) >= 0"로 작성하여 연산과정을 추가하였다.
• 따라서 이 2가지 요인을 다음과 같이 변경하였다.
  1. sys 라이브러리를 활용하여 입력받는다. sys.stdin.readline()은 input() 함수보다 빠르게 동작한다.(input()은 개행 문자 제거 및 문자열 변환 과정이 포함되기 때문에 상대적으로 느리다.)
  2. 조건문을 "if t > mid"로 변경하여 작성한다.

문제 풀 때 되도록이면 sys 라이브러리를 사용하자!!

import sys

input = sys.stdin.readline

n, m = map(int, input().split()) # n: 나무의 수, m: 집으로 가져가려고 하는 나무의 길이

tree = list(map(int, input().split())) # 나무들의 높이

start = 0
end = max(tree)

result = 0

while start <= end:
    mid = (start + end) // 2 # 절단기의 높이 설정

    carry = 0
    for t in tree:
        if t > mid:
            carry += (t - mid) # 절단기로 자른 후 가져갈 수 있는 나무의 길이를 더한다.

    if carry >= m:
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)